C & C++ Multimedia Cyber Classroom

home *** CD-ROM | disk | FTP | other *** search

/ C & C++ Multimedia Cyber Classroom / C and C++ Multimedia Cyber Classroom (Prentice Hall) (1998).iso / cpphtp2 / cpphtp2.jar / chpt_04.gml < prev next >

Wrap

Text File | 1998-03-03 | 145KB | 3,396 lines

<html> <chapter> <section type=Popup name=Quotes title="Quotes"> <page> With sobs and tears he sorted out Those of the largest size... Lewis Carroll </page> <page> Attempt the end, and never stand to doubt; Nothing's so hard, but search will find it out. Robert Herrick </page> <page> Now go, write it before them in a table, and note it in a book. Isaiah 30:8 </page> <page> 'Tis in my memory lock'd, And you yourself shall keep the key of it. William Shakespeare </page> </section> <section type=Popup name=Answers title="Answers"> <page pagename="Answers 4.1"> Answers 4.1 a) Arrays. b) Name, type. c) Subscript. d) Constant variable. e) Sorting. f) Searching. g) Double-subscripted. <foreign name="exercises" url="^Exercises::c:s0p0"> </page> <page pagename="Answers 4.2"> Answers 4.2 a) False. An array can store only values of the same type. b) False. An array subscript should normally be an integer or an integer expression. c) False. The remaining elements are automatically initialized to zero. d) True. e) False. Individual elements of an array are passed call-by-value. If the entire array is passed to a function, then any modifications will be reflected in the original. <foreign name="exercises" url="^Exercises::c:s0p2"> </page> <page pagename="Answers 4.3"> Answers 4.3 <pre> a) const int arraySize = 10; b) float fractions[ arraySize ] = { 0 }; c) fractions[ 3 ] d) fractions[ 4 ] e) fractions[ 9 ] = 1.667; f) fractions[ 6 ] = 3.333; g) cout << setiosflags( ios::fixed | ios::showpoint ) << setprecision( 2 ) << fractions[ 6 ] << ' ' << fractions[ 9 ] << endl; Output: 3.33 1.67. </pre> <foreign name="exercises" url="^Exercises::c:s0p3"> </page> <page pagename="Answers 4.3"> <pre> h) for ( int x = 0; x < arraySize; x++ ) cout << "fractions[" << x << "] = " << fractions[ x ] << endl; Output: fractions[ 0 ] = 0 fractions[ 1 ] = 0 fractions[ 2 ] = 0 fractions[ 3 ] = 0 fractions[ 4 ] = 0 </pre> <pre> fractions[ 5 ] = 0 fractions[ 6 ] = 3.333 fractions[ 7 ] = 0 fractions[ 8 ] = 0 fractions[ 9 ] = 1.667 </pre> <foreign name="exercises" url="^Exercises::c:s0p3"> </page> <page pagename="Answers 4.4"> Answers 4.4 <pre> a)<spacer width=20 height=1>int table[ arraySize ][ arraySize ]; </pre> b) Nine. <pre> c) for ( x = 0; x < arraySize; x++ ) <spacer width=20 height=1> for ( y = 0; y < arraySize; y++ ) <spacer width=20 height=1> table[ x ][ y ] = x + y; d) cout << " [0] [1] [2]" << endl; <spacer width=20 height=1>for ( int x = 0; x < arraySize; x++ ) { <spacer width=20 height=1> cout << '[' << x << "] "; <spacer width=20 height=1> for ( int y = 0; y < arraySize; y++ ) </pre> <foreign > <foreign name="exercises" url="^Exercises::c:s0p5"> </page> <page pagename="Answers 4.4"> <pre> <spacer width=20 height=1> [0] [1] [2] <spacer width=20 height=1>[0] 1 8 0 <spacer width=20 height=1>[1] 2 4 6 <spacer width=20 height=1>[2] 5 0 0 </pre> <foreign name="exercises" url="^Exercises::c:s0p5"> </page> <page pagename="Answers 4.5"> Answers 4.5 a) <spacer width=20 height=1>Error: Semicolon at end of #include preprocessor directive. <spacer width=20 height=1><spacer width=20 height=1>Correction: Eliminate semicolon. b) Error: Assigning a value to a constant variable using an assignment statement. Correction: Assign a value to the constant variable in a const int arraySize declaration. c) Error: Referencing an array element outside the bounds of the array ( b[10] ). Correction: Change the final value of the control variable to 9. d) Error: Array subscripting done incorrectly. Correction: Change the statement to a[ 1 ][ 1 ] = 5; <foreign name="exercises" url="^Exercises::c:s0p7"> </page> <page pagename="Answers 4.12"> Answers 4.12 a) int counts[ 10 ] = { 0 }; b) <pre> for ( int i = 0; i < 15; ++i ) ++bonus[ i ]; </pre> c) <pre> for ( int p = 0; p < 12; ++p ) cin >> monthlyTemperatures[ p ]; </pre> d) <pre> for ( int u = 0; u < 5; ++u ) cout << bestScores[ u ] << '\ '; </pre> <foreign name="exercises" url="^Exercises::c:s0p19"> </page> <page pagename="Answer 4.10 "> Answer 4.10 The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P4_10.zip to your hard drive and unzip the program code. <foreign name="exercises" url="^Exercises::c:s0p15"> </page> <page pagename="Answer 4.15 "> Answer 4.15 The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P4_15.zip to your hard drive and unzip the program code. <foreign name="exercises" url="^Exercises::c:s0p22"> </page> <page pagename="Answer 4.20 "> Answer 4.20 The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P4_20.zip to your hard drive and unzip the program code. <foreign name="exercises" url="^Exercises::c:s0p28"> </page> <page pagename="Answer 4.23 "> Answer 4.23 The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P4_23.zip to your hard drive and unzip the program code. <foreign name="exercises" url="^Exercises::c:s0p34"> </page> <page pagename="Answer 4.29 "> Answer 4.29 The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P4_29.zip to your hard drive and unzip the program code. <foreign name="exercises" url="^Exercises::c:s0p53"> </page> <page pagename="Answer 4.30 "> Answer 4.30 The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P4_30.zip to your hard drive and unzip the program code. <foreign name="exercises" url="^Exercises::c:s0p55"> </page> <page pagename="Answer 4.33 "> Answer 4.33 The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P4_33.zip to your hard drive and unzip the program code. <foreign name="exercises" url="^Exercises::c:s0p61"> </page> <page pagename="Answer 4.36 "> Answer 4.36 The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P4_36.zip to your hard drive and unzip the program code. <foreign name="exercises" url="^Exercises::c:s0p64"> </page> <page pagename="Answer 4.38 "> Answer 4.38 The solution to this exercise can be found on your Cyber Classroom CD. Copy the file cpphtp2/answers/P4_38.zip to your hard drive and unzip the program code. <foreign name="exercises" url="^Exercises::c:s0p66"> </page> </section> <section type=Body name=Default title="4 Arrays"> <page> 4 Arrays<hr> <a href="#s1p0">4.1<spacer width=20 height=1>Introduction</a> <a href="#s2p0">4.2<spacer width=20 height=1>Arrays</a> <a href="#s3p0">4.3<spacer width=20 height=1>Declaring Arrays</a> <a href="#s4p0">4.4<spacer width=20 height=1>Examples Using Arrays</a> <a href="#s5p0">4.5<spacer width=20 height=1>Passing Arrays to Functions</a> <a href="#s6p0">4.6<spacer width=20 height=1>Sorting Arrays</a> <a href="#s7p0">4.7<spacer width=20 height=1>Case Study: Computing Mean, Median, and Mode Using Arrays</a> <a href="#s8p0">4.8<spacer width=20 height=1>Searching Arrays: Linear Search and Binary Search</a> <foreign name="objectivesButton" url="^Objective::c:s0p0"> <foreign name="quotes" url="^Quotes::c:s0p0"> </page> <page> <a href="#s9p0">4.9<spacer width=20 height=1>Multiple-Subscripted Arrays</a> <a href="#s10p0">4.10<spacer width=20 height=1>Thinking About Objects: Identifying a Class's Behaviors</a> <a href="#s11p0">4.11<spacer width=20 height=1>Elevator Laboratory Assignment 3</a> <a href="#s12p0">4.12<spacer width=20 height=1>Summary</a> <a href="^Terminology::c:s0p0">Terminology</a> <a href="^Illustration::c:s0p0">Figures</a> <foreign name="objectivesButton" url="^Objective::c:s0p0"> <foreign name="quotes" url="^Quotes::c:s0p0"> </page> </section> <section type=Body name=Default title="4.1 Introduction"> <page> 4.1 Introduction<hr> This chapter serves as an introduction to the important topic of data structures. Arrays are data structures consisting of related data items of the same type. In Chapter 6, we discuss the notions of structures and classes--each capable of holding related data items of possibly different types. Arrays and structures are "static" entities in that they remain the same size throughout program execution (they may, of course, be of automatic storage class and hence created and destroyed each time the blocks in which they are defined are entered and exited). In Chapter 15, we </page> <page> introduce dynamic data structures such as lists, queues, stacks, and trees that may grow and shrink as programs execute. The style of arrays we use in this chapter are C-style pointer-based arrays (we will study pointers in Chapter 5). Later in the text in Chapter 8 on "Operator Overloading" and near the end of the book in the chapter entitled, "The Standard Template Library," we will cover arrays as full-fledged objects using the techniques of object-oriented programming. We will discover that these object-based arrays are safer and more versatile than the C-like, pointer-based arrays we discuss here in Chapter 4. </page> </section> <section type=Body name=Default title="4.2 Arrays"> <page> 4.2 Arrays<hr> An array is a consecutive group of memory locations that all have the same name and the same type. To refer to a particular location or element in the array, we specify the name of the array and the position number of the particular element in the array. <spacer width=16 height=1> <a href="^Illustration::c:s0p2"> <img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 4.1</a> shows an integer array called c. This array contains twelve elements. Any one of these elements may be referred to by giving the name of the array followed by the position number of the particular element in square brackets ([]). The first element in every array is the zeroth element. Thus, the first element </page> <page> of array c is referred to as c[0], the second element of array c is referred to as c[1], the seventh element of array c is referred to as c[6], and, in general, the ith element of array c is referred to as c[i - 1]. Array names follow the same conventions as other variable names. <spacer width=16 height=1>The position number contained within square brackets is more formally called a subscript. A subscript must be an integer or an integer expression. If a program uses an expression as a subscript, then the expression is evaluated to determine the subscript. For example, if we assume that variable a is equal to 5 and that variable b is equal to 6, then the statement <pre> c[ a + b ] += 2; </pre> adds 2 to array element c[ 11 ]. Note that a subscripted array name is an lvalue--it can be used on the left side of an assignment. <spacer width=16 height=1>Let us examine array c in <a href="^Illustration::c:s0p2"> <img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 4.1</a> more closely. The name of the entire array is c. Its twelve elements are </page> <page> named c[0], c[1], c[2], \xc9 , c[11]. The value of c[0] is - 45, the value of c[1] is 6, the value of c[2] is 0, the value of c[7] is 62, and the value of c[11] is 78. To print the sum of the values contained in the first three elements of array c, we would write <pre> cout << c[ 0 ] + c[ 1 ] + c[ 2 ] << endl; </pre> To divide the value of the <a href="^Errors::c:s0p0"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>seventh element of array c by 2 and assign the result to the variable x, we would write <pre> x = c[ 6 ] / 2; </pre> The brackets used to enclose the subscript of an array are actually an operator in C++. Brackets have the same </page> <page> level of precedence as parentheses. The chart in <a href="^Illustration::c:s0p3"> <img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 4.2</a> shows the precedence and associativity of the operators introduced so far. They are shown top to bottom in decreasing order of precedence with their associativity and type. </page> <page> Select the true statement(s). <component type="checkbox" width=20 height=18 label="" name="" feedback="False. A subscript must be an int or integer expression."> A subscript can be either of type int or type double. <component type="checkbox" width=20 height=18 label="" name="" feedback="False. The subscript must be contained in square brackets ([])."> An array element can be referenced by specifying the name of the array followed by a subscript contained in parentheses. <component type="checkbox" width=20 height=18 label="" name="" correct="True."> An array is a group of contiguous memory locations that all have the same name and the same type. <component type="checkbox" width=20 height=18 label="" name="" feedback="False. They have the same precedence."> Brackets have higher precedence than parentheses. <component type=button name=b label="Check Your Answer" width=125 height=24> </page> </section> <section type=Body name=Default title="4.3 Declaring Arrays"> <page> 4.3 Declaring Arrays<hr> Arrays occupy space in memory. The programmer specifies the type of each element and the number of elements required by each array so that the compiler may reserve the appropriate amount of memory. To tell the compiler to reserve 12 elements for integer array c, the declaration <pre> int c[ 12 ]; </pre> is used. Memory may be reserved for several arrays with a single declaration. The following declaration reserves 100 elements for the integer array b and 27 elements for the integer array x. </page> <page> <pre> int b[ 100 ], x[ 27 ]; </pre> Arrays may be declared to contain other data types. For example, an array of type char can be used to store a character string. Character strings and their similarity to arrays (a relationship C++ inherited from C), and the relationship between pointers and arrays, are discussed in Chapter 5. After we introduce object-oriented programming, we will consider strings as full-fledged objects. </page> <page> Select the true statement(s). <component type="checkbox" width=20 height=18 label="" name="" correct="True."> Memory may be reserved for several arrays with a single declaration. <component type="checkbox" width=20 height=18 label="" name="" feedback="False. Arrays can be declared for any data type."> Arrays can only be of data type int. <component type=button name=b label="Check Your Answer" width=125 height=24> </page> </section> <section type=Body name=Default title="4.4 Examples Using Arrays"> <page> 4.4 Examples Using Arrays<hr> The program in <a href="^Code::c:s0p0"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.3</a> uses a for repetition structure to initialize the elements of a ten-element integer array n to zeros, and prints the array in tabular format. The first output statement displays the column headings for the columns printed in the subsequent for structure. Remember that setw specifies the field width in which the next value is to be output. <spacer width=16 height=1>The elements of an array can also be initialized in the array declaration by following the declaration with an equal sign and a comma-separated list (enclosed in braces) of initializers. The program in <a href="^Code::c:s0p1"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.4</a> </page> <page> initializes an integer array with ten values and prints the array in tabular format. <spacer width=16 height=1>If there are fewer initializers than elements in the array, the remaining elements are automatically initialized to zero. For example, the elements of the array n in <a href="^Code::c:s0p0"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.3</a> could have been initialized to zero with the declaration <pre> int n[ 10 ] = { 0 }; </pre> which explicitly initializes the first element to zero and implicitly <a href="^Errors::c:s0p3"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>initializes the remaining nine elements to zero because there are fewer initializers than elements in the array. Remember that automatic arrays are not implicitly initialized to zero. The programmer must at </page> <page> least initialize the first element to zero for the remaining elements to be automatically zeroed. The method used in <a href="^Code::c:s0p0"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.3</a> can be performed repeatedly as a program executes. <spacer width=16 height=1>The following array declaration <pre> int n[ 5 ] = { 32, 27, 64, 18, 95, 14 }; </pre> would cause a syntax <a href="^Errors::c:s0p2"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>error because there are 6 initializers and only 5 array elements. <spacer width=16 height=1>If the array size is omitted from a declaration with an initializer list, the number of elements in the array will be the number of elements in the initializer list.<a href="^Perform::c:s0p0"> <img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>For example, <pre> int n[] = { 1, 2, 3, 4, 5 }; </pre> </page> <page> would create a five-element array. <spacer width=16 height=1>The program in <a href="^Code::c:s0p2"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.5</a> initializes the elements of a ten-element array s to the integers 2, 4, 6, ..., 20, and prints the array in tabular format. These numbers are generated by multiplying each successive value of the loop counter by 2 and adding 2. <spacer width=16 height=1>The line <pre> const int arraySize = 10; </pre> uses the const qualifier to declare a so-called constant variable arraySize the value of which is 10. Constant variables must be initialized with a constant expression when they are declared and cannot be modified thereafter (<a href="^Code::c:s0p4"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.6</a> and <a href="^Code::c:s0p3"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.7</a>). Constant variables </page> <page> are also called named constants or read-only variables. Note that the term "constant variable" is an oxymoron--a contradiction in terms like "jumbo shrimp" or "freezer burn." (Please send your favorite oxymorons to our email address listed in the Preface. Thanks!) <spacer width=16 height=1>Constant variables can be placed anywhere a <a href="^Errors::c:s0p4"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>constant expression is expected. In <a href="^Code::c:s0p2"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.5</a>, constant variable arraySize is used to specify the size of array s in the declaration <pre> int j, s[ arraySize ]; </pre> Using constant variables to specify array sizes makes programs more scalable. In <a href="^Code::c:s0p2"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.5</a>, the first for loop </page> <page> could fill a 1000-element array by simply changing the <a href="^Errors::c:s0p5"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>value of arraySize in its declaration from 10 to 1000. If the constant variable arraySize had not been used, we would have to change the program in three separate places to scale the program to handle 1000 array elements. As programs get larger, this technique becomes more useful for writing clear programs. <spacer width=16 height=1>The program in <a href="^Code::c:s0p5"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.8</a> sums the values contained in the twelve-element integer array a. The statement in the body of the for loop does the totaling. It is important to remember that the values being supplied as initializers <a href="^Engineer::c:s0p0"><img src="bckgrnds/icons/seo_ico.gif" align=sidebar></a>for array a normally would be read into the program </page> <page> from the user at the keyboard. For example, the <a href="^Practice::c:s0p0"><img src="bckgrnds/icons/gpp_ico.gif" align=sidebar></a>following for structure <pre> for ( int j = 0; j < arraySize; j++ ) cin >> a[ j ]; </pre> reads one value at a time from the keyboard and stores the value in element a[ j ]. <spacer width=16 height=1>Our next example uses arrays to summarize the results of data collected in a survey. Consider the problem statement: <indent width=16>Forty students were asked to rate the quality of the food in the student cafeteria on a scale of 1 to 10 (1 means awful and 10 means excellent). Place the 40 responses in an integer array and summarize the results of the poll.</indent> </page> <page> This is a typical array application (see <a href="^Code::c:s0p6"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.9</a>). We wish to summarize the number of responses of each type (i.e., 1 through 10). The array responses is a 40- element array of the students' responses. We use an eleven-element array frequency to count the number of <a href="^Practice::c:s0p3"><img src="bckgrnds/icons/gpp_ico.gif" align=sidebar></a>occurrences of each response. We ignore the first element, frequency[ 0 ], because it is more logical to have the r<a href="^Perform::c:s0p1"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>esponse 1 increment frequency[ 1 ] than frequency[ 0 ]. This allows us to use each response directly as a subscript on the frequency array. <spacer width=16 height=1>The first for loop takes the responses one at a time from the array responses and increments one of the ten </page> <page> counters (frequency[ 1 ] to frequency[ 10 ]) in the frequency array. The key statement in the loop is <pre> ++frequency[ responses[ answer ] ]; </pre> This statement increments the appropriate frequency counter depending on the value of responses[ answer ]. For example, when the counter answer is 0, the value of responses[ answer ] is 1, so ++frequency[ responses[ answer ] ]; is actually interpreted as <pre> ++frequency[ 1 ]; </pre> </page> <page> which increments array element one. When answer is 1, responses[ answer ] is 2, so ++frequency[ responses[ answer ] ]; is interpreted as <pre> ++frequency[ 2 ]; </pre> which increments array element two. When answer is 2, responses[ answer ] is 6, so ++frequency[ responses[ answer ] ]; is interpreted as <pre> ++frequency[ 6 ]; </pre> which increments array element six, and so on. Note that regardless of the number of responses processed in the survey, only an eleven-element array is required (ignoring element zero) to summarize the results. If the </page> <page> data contained invalid values such as 13, the program would attempt to add 1 to frequency[ 13 ]. This would be <a href="^Errors::c:s0p6"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>outside the bounds of the array. C++ has no array bounds checking to prevent the computer from referring to an element that does not exist. Thus, an executing <a href="^Debug::c:s0p3"><img src="bckgrnds/icons/dbt_ico.gif" align=sidebar></a>program can walk off either end of an array without warning. The programmer should ensure that all array references remain within the bounds of the array. C++ <a href="^Debug::c:s0p2"><img src="bckgrnds/icons/dbt_ico.gif" align=sidebar></a>is an extensible language. In Chapter 8, we will extend C++ by implementing an array as a user-defined type <a href="^Portable::c:s0p0"><img src="bckgrnds/icons/port_ico.gif" align=sidebar></a>with a class. Our new array definition will enable us to perform many operations that are not standard for C++'s built-in arrays. For example, we will be able to </page> <page> compare arrays directly, assign one array to another, input and output entire arrays with cin and cout, <a href="^Debug::c:s0p0"><img src="bckgrnds/icons/dbt_ico.gif" align=sidebar></a> initialize arrays automatically, prevent access to out-of- range array elements, and change the range of subscripts (and even their subscript type) so that the first element of an array is not required to be element 0. <spacer width=16 height=1>Our next example ( <a href="^Code::c:s0p7"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.10</a>) reads numbers from an array and graphs the information in the form of a bar chart or histogram--each number is printed, and then a bar consisting of that many asterisks is printed beside <a href="^Errors::c:s0p7"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>the number. The nested for loop actually draws the bars. Note the use of endl to end a histogram bar. </page> <page> In Chapter 3 we stated that we would show a more elegant method of writing the dice-rolling program of Fig. 3.8. The problem was to roll a single six-sided die 6000 times to test whether the random number generator actually produces random numbers. An array version of this program is shown in <a href="^Code::c:s0p8"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.11</a>. <spacer width=16 height=1>To this point we have discussed only integer arrays. However, arrays may be of any type. We now discuss <a href="^Debug::c:s0p5"><img src="bckgrnds/icons/dbt_ico.gif" align=sidebar></a>storing character strings in character arrays. So far, the only string processing capability we introduced is outputting a string with cout and <<. A string such as "hello" is really an array of characters. Character arrays have several unique features. </page> <page> A character array can be initialized using a string literal. For example, the declaration <pre> char string1[] = "first"; </pre> initializes the elements of array string1 to the individual characters in the string literal "first". The size of array string1 in the preceding declaration is determined by the compiler based on the length of the string. It is important to note that the string "first" contains five characters plus a special string termination character called the null character. Thus, array string1 actually contains six elements. The character constant representation of the null character is '\\0' (backslash followed by zero). All strings end with this character. A </page> <page> character array representing a string should always be declared large enough to hold the number of characters in the string and the terminating null character. <spacer width=16 height=1>Character arrays also can be initialized with individual character constants in an initializer list. The preceding declaration is equivalent to the more tedious form <pre> char string1[] = { 'f', 'i', 'r', 's', 't', '\\0' }; </pre> Because a string is an array of characters, we can access individual characters in a string directly using array subscript notation. For example, string1[0] is the character 'f' and string1[3] is the character 's'. </page> <page> We also can input a string directly into a character array from the keyboard using cin and >>. For example, the declaration <pre> char string2[ 20 ]; </pre> creates a character array capable of storing a string of 19 characters and a terminating null character. The statement <pre> cin >> string2; </pre> reads a string from the keyboard into string2. Note in the preceding statement that only the name of the array is <a href="^Errors::c:s0p8"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>supplied; no information about the size of the array is provided. It is the programmer's responsibility to </page> <page> ensure that the array into which the string is read is capable of holding any string the user types at the keyboard. cin reads characters from the keyboard until the first whitespace character is encountered--it does not care how large the array is. Thus, inputting data with cin and >> can insert data beyond the end of the array (see Section 5.12 for information on preventing insertion beyond the end of a char array). <spacer width=16 height=1>A character array representing a null-terminated string can be output with cout and <<. The array string2 is printed with the statement <pre> cout << string2 << endl; </pre> </page> <page> Note that cout <<, like cin >>, does not care how large the character array is. The characters of the string are printed until a terminating null character is encountered. <spacer width=16 height=1><a href="^Code::c:s0p9"> </a> <a href="^Code::c:s0p9"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 4.12 </a>demonstrates initializing a character array with a string literal, reading a string into a character array, printing a character array as a string, and accessing individual characters of a string. <spacer width=16 height=1> <a href="^Code::c:s0p9"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 4.12</a> uses a for structure to loop through the string1 array and print the individual characters separated by spaces. The condition in the for structure, string1[ i ] != '\\0', is true while the terminating null character has not been encountered in the string. </page> <page> Chapter 3 discussed the storage class specifier static. A static local variable in a function definition exists for <a href="^Perform::c:s0p2"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a> the duration of the program but is only visible in the function body. <spacer width=16 height=1>Arrays that are declared static are initialized when the program is loaded. If a static array is not explicitly initialized by the programmer, that array is initialized to zero by the compiler. <spacer width=16 height=1> <a href="^Code::c:s0p10"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 4.13</a> demonstrates function staticArrayInit with a local array declared static and function automaticArrayInit with an automatic local array. Function staticArrayInit is called twice. The static local array is initialized to zero by the compiler. The </page> <page> function prints the array, adds 5 to each element, and prints the array again. The second <a href="^Errors::c:s0p9"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>time the function is called, the static array contains the values stored during the first function call. Function automaticArrayInit is also called twice. The elements of the automatic local array are initialized with the values 1, 2, and 3. The function prints the array, adds 5 to each element, and prints the array again. The second time the function is called, the array elements are re-initialized to 1, 2, and 3 because the array has automatic storage class. </page> <page> Select the true statement(s). <component type="checkbox" width=20 height=18 label="" name="" feedback="False. Array elements can be initialized in a declaration using an initializer list in braces."> Array elements cannot be initialized in a declaration. <component type="checkbox" width=20 height=18 label="" name="" correct="True."> The array size can be determined by the number of elements in an initializer list. <component type="checkbox" width=20 height=18 label="" name="" correct="True."> The keyword const is used to declare a constant variable. <component type="checkbox" width=20 height=18 label="" name="" feedback="False. Arrays of type char can be initialized with initializer lists or with C-style strings."> Arrays of type char cannot be initialized with initializer lists. <component type=button name=b label="Check Your Answer" width=125 height=24> </page> </section> <section type=Body name=Default title="4.5 Passing Arrays to Functions"> <page> 4.5 Passing Arrays to Functions<hr> To pass an array argument to a function, specify the name of the array without any brackets. For example, if array hourlyTemperatures has been declared as <pre> int hourlyTemperatures[ 24 ]; </pre> the function call statement <pre> modifyArray( hourlyTemperatures, 24 ); </pre> passes array hourlyTemperatures and its size to function modifyArray. When passing an array to a function, the array size is normally passed as well so the function can process the specific number of elements in the array (otherwise, we would need to build this </page> <page> knowledge into the called function itself, or worse yet place the array size in a global variable). In Chapter 8, when we introduce the Array class, we will build the size of the array into the user-defined type--every Array object that we create will "know" its own size. Thus, when we pass an Array object into a function we no longer will have to pass the size of the array as an argument. <spacer width=16 height=1>C++ automatically passes arrays to <a href="^Perform::c:s0p4"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>functions using simulated call-by-reference--the called functions can <a href="^Engineer::c:s0p1"><img src="bckgrnds/icons/seo_ico.gif" align=sidebar></a>modify the element values in the callers' original arrays. The value of the name of the array is the address of the first element of the array. Because the starting </page> <page> address of the array is passed, the called function knows precisely where the array is stored. Therefore, when the called function modifies array elements in its function body, it is modifying the actual elements of the array in their original memory locations. <spacer width=16 height=1>Although entire arrays are passed simulated call-by- reference, individual array elements are passed call-by- value exactly as simple variables are. Such simple single pieces of data are called scalars or scalar quantities. To pass an element of an array to a function, use the subscripted name of the array element as an argument in the function call. In Chapter 5, we show </page> <page> how to simulate call-by-reference for scalars (i.e., individual variables and array elements). <spacer width=16 height=1>For a function to receive an array through a function call, the function's parameter list must specify that an array will be received. For example, the function header for function modifyArray might be written as <pre> void modifyArray( int b[], int arraySize ) </pre> indicating that modifyArray expects to receive an array of integers in parameter b and the number of array elements in parameter arraySize. The size of the array is not required between the array brackets. If it is included, the compiler will ignore it. Because arrays are passed simulated call-by-reference, when the called </page> <page> function uses the array name b, it will in fact be referring to the actual array in the caller (array hourlyTemperatures in the preceding call). In Chapter 5, we introduce other notations for indicating that an array is being received by a function. As we will see, these notations are based on the intimate relationship between arrays and pointers. <spacer width=16 height=1> <a href="^Practice::c:s0p4"><img src="bckgrnds/icons/gpp_ico.gif" align=sidebar></a>Note the strange appearance of the function prototype for modifyArray <pre> void modifyArray( int [], int ); </pre> This prototype could have been written <pre> void modifyArray( int anyArrayName[], int anyVariableName ) </pre> </page> <page> but as we learned in Chapter 3, C++ compilers ignore variable names in prototypes. <spacer width=16 height=1>Remember, the prototype tells the compiler the number of arguments and the types of each argument (in the order in which the arguments are expected to appear). <spacer width=16 height=1>The program in <a href="^Code::c:s0p11"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.14</a> demonstrates the difference between passing an entire array and passing an array element. The program first prints the five elements of integer array a. Next, a and its size are passed to function modifyArray where each of a's elements is multiplied by 2. Then a is reprinted in main. As the output shows, the elements of a are indeed modified by modifyArray. Now the program prints the value of </page> <page> a[3] and passes it to function modifyElement. Function modifyElement multiplies its argument by 2 and prints the new value. Note that when a[3] is reprinted in main, it has not been modified because individual array elements are passed call-by-value. <spacer width=16 height=1>There may be situations in your programs in which a function should not be allowed to modify array elements. Because arrays are always passed simulated call-by-reference, modification of values in an array is difficult to control. C++ provides the type qualifier const that can be used to prevent modification of array values in a function. When an array parameter is preceded by the const qualifier, the elements of the </page> <page> array become constant in the function body, and any attempt to modify an element of the array in the function body results in a syntax error. This enables the programmer to correct a program so it does not attempt to modify array elements. <spacer width=16 height=1> <a href="^Code::c:s0p12"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 4.15</a> demonstrates the const <a href="^Errors::c:s0p10"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>qualifier. Function tryToModifyArray is defined with parameter const int b[] which specifies that array b is constant and cannot be <a href="^Engineer::c:s0p2"><img src="bckgrnds/icons/seo_ico.gif" align=sidebar></a>modified. Each of the three attempts by the function to modify array elements results in the syntax error "Cannot modify a const object." The const qualifier will be discussed again in Chapter 7. </page> <page> Select the true statement(s). <component type="checkbox" width=20 height=18 label="" name="" correct="True."> When an argument is passed call-by-value, a copy of the argument's value is passed. <component type="checkbox" width=20 height=18 label="" name="" correct="True."> Call-by-reference gives called functions the ability to directly access the caller's data. <component type="checkbox" width=20 height=18 label="" name="" feedback="False. Arrays are passed call-by-reference by default. All other types of data are passed-by-value by default."> Arrays are passed call-by-value by default. <component type=button name=b label="Check Your Answer" width=125 height=24> </page> </section> <section type=Body name=Default title="4.6 Sorting Arrays"> <page> 4.6 Sorting Arrays<hr> Sorting data (i.e., placing the data into some particular order such as ascending or descending) is one of the most important computing applications. A bank sorts all checks by account number so that it can prepare individual bank statements at the end of each month. Telephone companies sort their lists of accounts by last name and, within that, by first name to make it easy to find phone numbers. Virtually every organization must sort some data and in many cases massive amounts of data. Sorting data is an intriguing problem which has attracted some of the most intense research efforts in </page> <page> the field of computer science. In this chapter we discuss <a href="^Perform::c:s0p6"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>the simplest known sorting scheme. In the exercises and in Chapter 15, we investigate more complex schemes that yield superior performance. <spacer width=16 height=1>The program in <a href="^Code::c:s0p13"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.16</a> sorts the values of the ten- element array a into ascending order. The technique we use is called the bubble sort or the sinking sort because the smaller values gradually "bubble" their way upward to the top of the array like air bubbles rising in water, while the larger values sink to the bottom of the array. The technique is to make several passes through the array. On each pass, successive pairs of elements are compared. If a pair is in increasing order (or the values </page> <page> are identical), we leave the values as they are. If a pair is in decreasing order, their values are swapped in the array. <spacer width=16 height=1>First the program compares a[ 0 ] to a[ 1 ], then a[ 1 ] to a[ 2 ], then a[ 2 ] to a[ 3 ], and so on until it completes the pass by comparing a[ 8 ] to a[ 9 ]. Although there are 10 elements, only nine comparisons are performed. Because of the way the successive comparisons are made, a large value may move down the array many positions on a single pass, but a small value may move up only one position. On the first pass, the largest value is guaranteed to sink to the bottom element of the array, a[ 9 ]. On the second pass, the </page> <page> second largest value is guaranteed to sink to a[ 8 ]. On the ninth pass, the ninth largest value sinks to a[ 1 ]. This leaves the smallest value in a[ 0 ], so only nine passes are needed to sort a 10-element array. <spacer width=16 height=1>The sorting is performed by the nested for loop. If a swap is necessary, it is performed by the three assignments <pre> hold = a[ i ]; a[ i ] = a[ i + 1 ]; a[ i + 1 ] = hold; </pre> where the extra variable hold temporarily stores one of the two values being swapped. The swap cannot be performed with only the two assignments </page> <page> <pre> a[ i ] = a[ i + 1 ]; a[ i + 1 ] = a[ i ]; </pre> If, for example, a[i] is 7 and a[i + 1] is 5, after the first assignment both values will be 5 and the value 7 will be lost. Hence the need for the extra variable hold. <spacer width=16 height=1>The chief virtue of the bubble sort is that it is easy to program. However, the bubble sort runs slowly. This becomes apparent when sorting large arrays. In the exercises, we will develop more efficient versions of the bubble sort and investigate some far more efficient sorts than the bubble sort. More advanced courses investigate sorting and searching in greater depth. </page> <page> Select the true statement(s). <component type="checkbox" width=20 height=18 label="" name="" feedback="False. The bubble sort is inefficient for large arrays."> The bubble sort is efficient for sorting large arrays. <component type="checkbox" width=20 height=18 label="" name="" correct="True."> The bubble sort algorithm specifies that to sort n numbers, n - 1 passes and n - 1 comparisons per pass must be made. <component type="checkbox" width=20 height=18 label="" name="" correct="True."> The bubble sort is also called a sink sort. <component type=button name=b label="Check Your Answer" width=125 height=24> </page> </section> <section type=Body name=Default title="4.7 Case Study: Computing Mean, Median, and Mode Using Arrays"> <page> 4.7 Case Study: Computing Mean, Median, and Mode Using Arrays<hr> We now consider a larger example. Computers are commonly used to compile and analyze the results of surveys and opinion polls. The program in <a href="^Code::c:s0p14"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.17</a> uses array response initialized with 99 responses (represented by constant variable responseSize) to a survey. Each of the responses is a number from 1 to 9. The program computes the mean, median, and mode of the 99 values. </page> <page> The mean is the arithmetic average of the 99 values. Function mean computes the mean by totaling the 99 elements and dividing the result by 99. <spacer width=16 height=1>The median is the "middle value." Function median determines the median by calling function bubbleSort to sort the array of responses into ascending order, and picking the middle element, answer[responseSize / 2], of the sorted array. Note that when there is an even number of elements, the median should be calculated as the mean of the two middle elements. Function median does not currently provide this capability. Function printArray is called to output the response array. </page> <page> The mode is the value that occurs most frequently among the 99 responses. Function mode counts the number of responses of each type, then selects the value with the greatest count. This version of function mode does not handle a tie (see <a href="^Exercises::c:s0p21"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 4.14</a>). Function mode also produces a histogram to aid in determining the mode graphically.<a href="^Code::c:s0p14"> <img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 4.18</a> contains a sample run of this program. This example includes most of the common manipulations usually required in array problems, including passing arrays to functions. </page> </section> <section type=Body name=Default title="4.8 Searching Arrays: Linear Search and Binary Search"> <page> 4.8 Searching Arrays: Linear Search and Binary Search<hr> Often, a programmer will be working with large amounts of data stored in arrays. It may be necessary to determine whether an array contains a value that matches a certain key value. The process of finding a particular element of an array is called searching. In this section we discuss two searching techniques--the simple linear search technique and the more efficient binary search technique. <a href="^Exercises::c:s0p61"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercises 4.33</a> and <a href="^Exercises::c:s0p62"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>4.34</a> at the end of this chapter ask you to implement recursive versions of the linear search and the binary search. </page> <page> The linear search (<a href="^Code::c:s0p15"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.19</a>) compares each element of the array with the search key. Since the array is not in any particular order, it is just as likely that the value will be found in the first element as the last. On average, therefore, the program must compare the search key with half the elements of the array for a value in the array. To determine that a value is not in the array, the program must compare the search key to every element in the array. <spacer width=16 height=1>The linear searching method works well for small arrays or for unsorted arrays. However, for large arrays linear searching is inefficient. If the array is sorted, the high-speed binary search technique can be used. </page> <page> The binary search algorithm eliminates one half of the elements in the array being searched after each comparison. The algorithm locates the middle element of the array and compares it to the search key. If they are equal, the search key is found and the array subscript of that element is returned. Otherwise, the problem is reduced to searching one half of the array. If the search key is less than the middle element of the array, the first half of the array is searched, otherwise the second half of the array is searched. If the search key is not the middle element in the specified subarray (piece of the original array), the algorithm is repeated on one quarter of the original array. The search </page> <page> continues until the search key is equal to the middle element of a subarray or until the subarray consists of one element that is not equal to the search key (i.e., the search key is not found). <spacer width=16 height=1>In a worst case scenario, searching an array of 1024 elements will take only 10 comparisons using a binary search. Repeatedly dividing 1024 by 2 (because after each comparison we are able to eliminate half of the array) yields the values 512, 256, 128, 64, 32, 16, 8, 4, 2, and 1. The number 1024 (210) is divided by 2 only ten times to get the value 1. Dividing by 2 is equivalent to one comparison in the binary search algorithm. An array of 1048576 (220) elements takes a maximum of 20 </page> <page> comparisons to find the search key. An array of one billion elements takes a maximum of 30 comparisons to find the search key. This is a tremendous increase in <a href="^Perform::c:s0p7"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar> </a>performance over the linear search that required comparing the search key to an average of half the elements in the array. For a one billion element array, this is a difference between an average of 500 million comparisons and a maximum of 30 comparisons! The maximum number of comparisons needed for the binary search of any sorted array can be determined by finding the first power of 2 greater than the number of elements in the array. </page> <page> <a href="^Code::c:s0p16"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 4.20</a> presents the iterative version of function binarySearch. The function receives four arguments-- an integer array b, an integer searchKey, the low array subscript, and the high array subscript. If the search key does not match the middle element of a subarray, the low subscript or high subscript is adjusted so a smaller subarray can be searched. If the search key is less than the middle element, the high subscript is set to middle - 1, and the search is continued on the elements from low to middle - 1. If the search key is greater than the middle element, the low subscript is set to middle + 1, and the search is continued on the elements from middle + 1 to high. The program uses an array of 15 </page> <page> elements. The first power of 2 greater than the number of elements in this array is 16 (24), so a maximum of 4 comparisons are required to find the search key. Function printHeader outputs the array subscripts and function printRow outputs each subarray during the binary search process. The middle element in each subarray is marked with an asterisk (*) to indicate the element to which the search key is compared. </page> <page> Select the true statement(s). <component type="checkbox" width=20 height=18 label="" name="" correct="True."> The maximum number of comparisons needed for the binary search of any sorted array is the exponent for the first power of 2 greater than the number of elements in the array. <component type="checkbox" width=20 height=18 label="" name="" feedback="False. The process is known as searching."> The process of locating a particular element value in an array is called sorting. <component type="checkbox" width=20 height=18 label="" name="" correct="True."> The linear search method works well for small arrays or for unsorted arrays. <component type=button name=b label="Check Your Answer" width=125 height=24> </page> </section> <section type=Body name=Default title="4.9 Multiple-Subscripted Arrays"> <page> 4.9 Multiple-Subscripted Arrays<hr> Arrays in C++ can have multiple subscripts. A common use of multiple-subscripted arrays is to represent tables of values consisting of information arranged in rows and columns. To identify a particular table element, we must specify two subscripts: The first (by convention) identifies the element's row, and the second (by convention) identifies the element's column. <spacer width=16 height=1>Tables or arrays that require two subscripts to identify a particular element are called double-subscripted arrays. Note that multiple-subscripted arrays can have more than two subscripts. C++ compilers support at least 12 </page> <page> array subscripts. <a href="^Illustration::c:s0p4"> <img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 4.21</a> illustrates a double- subscripted array, a. The array contains three rows and four columns, so it is said to be a 3-by-4 array. In general, an array with m rows and n columns is called an m-by-n array. <spacer width=16 height=1>Every element in array a is identified in <a href="^Illustration::c:s0p4"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 4.21</a> by an element name of the form a[ i ][ j ]; a is the name of the array, and i and j are the subscripts that uniquely <a href="^Errors::c:s0p11"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>identify each element in a. Notice that the names of the elements in the first row all have a first subscript of 0; the names of the elements in the fourth column all have a second subscript of 3. </page> <page> A multiple-subscripted array can be initialized in its declaration much like a single subscripted array. For example, a double-subscripted array b[ 2 ][ 2 ] could be declared and initialized with <pre> int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; </pre> The values are grouped by row in braces. So, 1 and 2 initialize b[ 0 ][ 0 ] and b[ 0 ][ 1 ], and 3 and 4 initialize b[ 1 ][ 0 ] and b[ 1 ][ 1 ]. If there are not enough initializers for a given row, the remaining elements of that row are initialized to 0. Thus, the declaration <pre> int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } }; </pre> </page> <page> would initialize b[ 0 ][ 0 ] to 1, b[ 0 ][ 1 ] to 0, b[ 1 ][ 0 ] to 3 and b[ 1 ][ 1 ] to 4. <spacer width=16 height=1> <a href="^Code::c:s0p17"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 4.22</a> demonstrates initializing double- subscripted arrays in declarations. The program declares three arrays, each with two rows and three columns. The declaration of array1 provides six initializers in two sublists. The first sublist initializes the first row of the array to the values 1, 2, and 3; and the second sublist initializes the second row of the array to the values 4, 5, and 6. If the braces around each sublist are removed from the array1 initializer list, the compiler automatically initializes the elements of the first row followed by the elements of the second row. </page> <page> The declaration of array2 provides five initializers. The initializers are assigned to the first row then the second row. Any elements that do not have an explicit initializer are initialized to zero automatically, so array2[ 1 ][ 2 ] is initialized to 0. <spacer width=16 height=1>The declaration of array3 provides three initializers in two sublists. The sublist for the first row explicitly initializes the first two elements of the first row to 1 and 2. The third element is automatically initialized to zero. The sublist for the second row explicitly initializes the first element to 4. The last two elements are automatically initialized to zero. </page> <page> The program calls function printArray to output each array's elements. Notice that the function definition specifies the array parameter as int a[][ 3 ]. When we receive a single-subscripted array as an argument to a function, the array brackets are empty in the function's parameter list. The size of the first subscript of a multiple-subscripted array is not required either, but all subsequent subscript sizes are required. The compiler uses these sizes to determine the locations in memory of elements in multiple-subscripted arrays. All array elements are stored consecutively in memory regardless of the number of subscripts. In a double-subscripted </page> <page> array, the first row is stored in memory followed by the second row. <spacer width=16 height=1>Providing the subscript values in a parameter declaration enables the compiler to tell the function how to locate an element in the array. In a double- subscripted array, each row is basically a single- subscripted array. To locate an element in a particular row, the function must know exactly how many elements are in each row so it can skip the proper number of memory locations when accessing the array. Thus, when accessing a[ 1 ][ 2 ], the function knows to skip the first row's three elements in memory to get to </page> <page> the second row (row 1). Then, the function accesses the third element of that row (element 2). <spacer width=16 height=1>Many common array manipulations use for repetition structures. For example, the following for structure sets all the elements in the third row of array a in <a href="^Illustration::c:s0p4"> <img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 4.21</a> to zero: <pre> for ( column = 0; column < 4; column++ ) a[ 2 ][ column ] = 0; </pre> We specified the third row, therefore we know that the first subscript is always 2 (0 is the first row subscript, and 1 is the second row subscript). The for loop varies only the second subscript (i.e., the column subscript). </page> <page> The preceding for structure is equivalent to the assignment statements: <pre> a[ 2 ][ 0 ] = 0; a[ 2 ][ 1 ] = 0; a[ 2 ][ 2 ] = 0; a[ 2 ][ 3 ] = 0; </pre> The following nested for structure determines the total of all the elements in array a. <pre> total = 0; for ( row = 0; row < 3; row++ ) for ( column = 0; column < 4; column++ ) total += a[ row ][ column ]; </pre> </page> <page> The for structure totals the elements of the array one row at a time. The outer for structure begins by setting row (i.e., the row subscript) to 0 so the elements of the first row may be totaled by the inner for structure. The outer for structure then increments row to 1, so the elements of the second row can be totaled. Then, the outer for structure increments row to 2, so the elements of the third row can be totaled. The result is printed when the nested for structure terminates. <spacer width=16 height=1>The program of <a href="^Code::c:s0p18"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.23</a> performs several other common array manipulations on 3-by-4 array studentGrades. Each row of the array represents a student and each column represents a grade on one of </page> <page> the four exams the students took during the semester. The array manipulations are performed by four functions. Function minimum determines the lowest grade of any student for the semester. Function maximum determines the highest grade of any student for the semester. Function average determines a particular student's semester average. Function printArray outputs the double-subscripted array in a neat, tabular format. <spacer width=16 height=1>Functions minimum, maximum, and printArray each receive three arguments--the studentGrades array (called grades in each function), the number of students (rows of the array), and the number of exams (columns </page> <page> of the array). Each function loops through array grades using nested for structures. The following nested for structure is from the function minimum definition: <pre> for ( i = 0; i < pupils; i++ ) for ( j = 0; j < tests; j++ ) if ( grades[ i ][ j ] < lowGrade ) lowGrade = grades[ i ][ j ]; </pre> The outer for structure begins by setting i (i.e., the row subscript) to 0 so the elements of the first row can be compared to variable lowGrade in the body of the inner for structure. The inner for structure loops through the four grades of a particular row and compares each grade to lowGrade. If a grade is less </page> <page> than lowGrade, lowGrade is set to that grade. The outer for structure then increments the row subscript to 1. The elements of the second row are compared to variable lowGrade. The outer for structure then increments the row subscript to 2. The elements of the third row are compared to variable lowGrade. When execution of the nested structure is complete, lowGrade contains the smallest grade in the double- subscripted array. Function maximum works similarly to function minimum. <spacer width=16 height=1>Function average takes two arguments--a single- subscripted array of test results for a particular student and the number of test results in the array. When </page> <page> average is called, the first argument is studentGrades[ student ] which specifies that a particular row of the double-subscripted array studentGrades is to be passed to average. For example, the argument studentGrades[ 1 ] represents the four values (a single- subscripted array of grades) stored in the second row of the double-subscripted array studentGrades. A double-subscripted array could be considered an array with elements that are single-subscripted arrays. Function average calculates the sum of the array elements, divides the total by the number of test results, and returns the floating-point result. </page> <page> Select the true statement(s). <component type="checkbox" width=20 height=18 label="" name="" feedback="False. Multiple-subscripted arrays can have more than two subscripts."> Multiple-subscripted arrays always have two subscripts (i.e., two dimensions). <component type="checkbox" width=20 height=18 label="" name="" correct="True."> Multiple-subscripted arrays can be initialized with initializer lists. <component type=button name=b label="Check Your Answer" width=125 height=24> </page> </section> <section type=Body name=Default title="4.10 Thinking About Objects: Identifying a Class's Behaviors"> <page> 4.10 Thinking About Objects: Identifying a Class's Behaviors<hr> In the "Thinking About Objects" sections at the ends of Chapters 2 and 3, we performed the first two phases of an object-oriented design for our elevator simulator, namely identifying the classes needed to implement the simulator and identifying the attributes of those classes. <spacer width=16 height=1>In this assignment we concentrate on determining the behaviors of the classes needed to implement the elevator simulator. In Chapter 5, we will concentrate on the interactions between the objects of these classes. </page> <page> Let us consider the behaviors of some real-world class objects. A radio's behaviors include having its station set and having its volume set. A car's behaviors include accelerating (by pressing the accelerator pedal) and decelerating (by pressing the brake pedal). <spacer width=16 height=1>As we will see, objects do not ordinarily perform their behaviors spontaneously. Rather, a specific behavior is normally invoked when a message is sent to the object, requesting that the object perform that specific behavior. This sounds like a function call--precisely how messages are sent to objects in C++. </page> </section> <section type=Body name=Default title="4.11 Elevator Laboratory Assignment 3 "> <page> 4.11 Elevator Laboratory Assignment 3 <hr> 1. Continue working with the facts file you created in Chapter 3. You had separated the facts related to each class into two groups. You labeled the first group Attributes and the second group Other Facts. <spacer width=16 height=1>2. For each class, add a third group called Behaviors. Place in this group every behavior of a class that can be invoked by telling an object of that class to do something, i.e., by sending the object a message. For example, a button can be pushed (by a person), so list pushButton as a behavior of class button. Function pushButton and the other behaviors of class button are </page> <page> called member functions (or methods) of class button. The class's attributes (such as whether a button is "on" or "off") are called data members of class button. A class's member functions typically manipulate the class's data members (such as pushButton changing one of the button's attributes to "on"). Member functions also typically send messages to objects of other classes (such as a button object sending a comeGetMe message to summon the elevator). Assume that the elevator will have a button that is illuminated when someone presses it. When the elevator arrives at a floor, the elevator will want to send a resetButton message to turn the button's light off. The elevator may want to determine if a </page> <page> particular button has been pressed, so we can provide another behavior called getButton which simply examines a button and returns 1 or 0 to indicate that the button is currently "on" or "off." You will probably want the elevator's door to respond to messages openDoor and closeDoor. And so on. <spacer width=16 height=1>3. For each behavior you assign to a class, provide a brief description of what the behavior does. List any attribute changes the behavior causes, and list any messages the behavior sends to objects of other classes. </page> <page pagename="Notes "> Notes 1. Begin by listing the class behaviors that are explicitly mentioned in the problem statement. Then list behaviors that are directly implied in the problem statement. 2. Add appropriate behaviors as it becomes apparent they are needed. 3. Again, system design is not a perfect and complete process, so do the best you can for now and be prepared to modify your design as you proceed with this exercise in subsequent chapters. </page> <page pagename="Notes "> 4. As we will see, it is difficult to glean all possible behaviors at this phase of the design. You will probably add behaviors to your classes as you continue this exercise in Chapter 5. </page> </section> <section type=Body name=Default title="4.12 Summary"> <page> 4.12 Summary<hr> <indent width=8 delay>* C++ stores lists of values in arrays. An array is a consecutive group of related memory locations. These locations are related by the fact that they all have the same name and the same type. To refer to a particular location or element within the array, we specify the name of the array and the subscript.</indent> <indent width=8 delay>* A subscript may be an integer or an integer expression. Subscript expressions are evaluated to determine the particular element of the array.</indent> <indent width=8 delay>* It is important to note the difference when referring to the seventh element of the array as opposed to array </indent> </page> <page> <indent width=8 delay>* element seven. The seventh element has a subscript of 6, while array element seven has a subscript of 7 (actually the eighth element of the array). This is a source of "off-by-one" errors.</indent> <indent width=8 delay>* Arrays occupy space in memory. To reserve 100 elements for integer array b and 27 elements for integer array x, the programmer writes</indent> <pre> int b[ 100 ], x[ 27 ]; </pre> <indent width=8 delay>* An array of type char can be used to store a character string. </indent> <indent width=8 delay>* The elements of an array can be initialized: by declaration, by assignment, and by input.</indent> <indent width=8 delay>* If there are fewer initializers than elements in the </indent> </page> <page> <indent width=8 delay>* array, the remaining elements are initialized to zero. </indent> <indent width=8 delay>* C++ does not prevent referencing elements beyond the bounds of an array. </indent> <indent width=8 delay>* A character array can be initialized using a string literal.</indent> <indent width=8 delay>* All strings end with the null character ('\\0').</indent> <indent width=8 delay>* Character arrays can be initialized with character constants in an initializer list. </indent> <indent width=8 delay>* Individual characters in a string stored in an array can be accessed directly using array subscript notation. </indent> <indent width=8 delay>* To pass an array to a function, the name of the array is passed. To pass a single element of an array to a function, simply pass the name of the array followed by the </indent> </page> <page> <indent width=8 delay>* subscript (contained in square brackets) of the particular element.</indent> <indent width=8 delay>* Arrays are passed to functions using simulated call- by-reference--the called functions can modify the element values in the callers' original arrays. The value of the name of the array is the address of the first element of the array. Because the starting address of the array is passed, the called function knows precisely where the array is stored. </indent> <indent width=8 delay>* To receive an array argument, the function's parameter list must specify that an array will be received. The size of the array is not required in the array brackets.</indent> <indent width=8 delay>* C++ provides the type qualifier const that enables </indent> </page> <page> <indent width=8 delay>* programs to prevent modification of array values in a function. When an array parameter is preceded by the const qualifier, the elements of the array become constant in the function body, and any attempt to modify an element of the array in the function body is a syntax error. </indent> <indent width=8 delay>* An array can be sorted using the bubble-sort technique. Several passes of the array are made. On each pass, successive pairs of elements are compared. If a pair is in order (or the values are identical), it is left as is. If a pair is out of order, the values are swapped. For small arrays, the bubble sort is acceptable, but for larger arrays it is inefficient compared to other more sophisti</indent> </page> <page> <indent width=8 delay>* cated sorting algorithms. </indent> <indent width=8 delay>* The linear search compares each element of the array with the search key. If the array is not in any particular order, it is just as likely that the value will be found in the first element as the last. On average, therefore, the program will have to compare the search key with half the elements of the array. The linear searching method works well for small arrays and is acceptable for unsorted arrays. </indent> <indent width=8 delay>* Binary search eliminates from consideration half the elements in the array after each comparison by locating the middle element of the array and comparing it to the search key. If they are equal, the search key is found </indent> </page> <page> <indent width=8 delay>* and the array subscript of that element is returned. Otherwise, the problem is reduced to searching one half of the array.</indent> <indent width=8 delay>* In a worst case scenario, searching an array of 1024 elements will take only 10 comparisons using a binary search. </indent> <indent width=8 delay>* Arrays may be used to represent tables of values consisting of information arranged in rows and columns. To identify a particular element of a table, two subscripts are specified: The first (by convention) identifies the row in which the element is contained, and the second (by convention) identifies the column in which the element is contained. Tables or arrays that require two </indent> </page> <page> <indent width=8 delay>* subscripts to identify a particular element are called double-subscripted arrays. </indent> <indent width=8 delay>* When we receive a single-subscripted array as an argument to a function, the array brackets are empty in the function's parameter list. The size of the first subscript of a multiple-subscripted array is not required either, but all subsequent subscript sizes are required. The compiler uses these sizes to determine the locations in memory of elements in multiple-subscripted arrays. </indent> <indent width=8 delay>* To pass one row of a double-subscripted array to a function that receives a single-subscripted array, simply pass the name of the array followed by the first subscript.</indent> </page> </section> <section type=Popup name=Debug title="Testing"> <page> When we study classes (beginning with Chapter 6), we will see how to develop a "smart array" which automatically checks that all subscript references are in bounds at run-time. Using such smart data </page> <page> types helps eliminate bugs. </page> <page> Programs should validate the correctness of all input values to prevent erroneous information from affecting a program's calculations. </page> <page> When looping through an array, the array subscript should never go below 0 and should always be less than the total number of elements in the array (one less than the size of the array). Make sure the loop terminating </page> <page> condition prevents accessing elements outside this range. </page> <page> Although it is possible to modify a loop counter in a for body, avoid doing so because this often leads to subtle bugs. </page> </section> <section type=Popup name=Terminology title="Terminology"> <page> A array <a href="%s1p0"><img src=iicons/bullbib.gif></a> <a href="%s3p0"><img src=iicons/bullbib.gif></a> array initializer list <a href="^Errors::c:s0p2"><img src=iicons/bullbib.gif></a> B binary search <a href="%s8p0"><img src=iicons/bullbib.gif></a> <a href="%s8p0"><img src=iicons/bullbib.gif></a> <a href="%s8p1"><img src=iicons/bullbib.gif></a> <a href="^Perform::c:s0p7"><img src=iicons/bullbib.gif></a> bounds checking <a href="%s4p10"><img src=iicons/bullbib.gif></a> bubble sort <a href="%s6p1"><img src=iicons/bullbib.gif></a> <a href="%s6p4"><img src=iicons/bullbib.gif></a> <a href="^Exercises::c:s0p17"><img src=iicons/bullbib.gif></a> C column subscript <a href="^Illustration::c:s0p4"><img src=iicons/bullbib.gif></a> const <a href="%s5p6"><img src=iicons/bullbib.gif></a> constant variable <a href="%s4p3"><img src=iicons/bullbib.gif></a> <a href="^Engineer::c:s0p0"><img src=iicons/bullbib.gif></a> <a href="^Practice::c:s0p0"><img src=iicons/bullbib.gif></a> D </page> <page> double-subscripted array <a href="%s9p0"><img src=iicons/bullbib.gif></a> <a href="%s9p3"><img src=iicons/bullbib.gif></a> <a href="%s9p5"><img src=iicons/bullbib.gif></a> <a href="%s9p12"><img src=iicons/bullbib.gif></a> <a href="^Exercises::c:s0p32"><img src=iicons/bullbib.gif></a> E element of an array <a href="%s2p0"><img src=iicons/bullbib.gif></a> I initializer <a href="%s4p0"><img src=iicons/bullbib.gif></a> M magic number <a href="^Practice::c:s0p0"><img src=iicons/bullbib.gif></a> m-by-n array <a href="%s9p1"><img src=iicons/bullbib.gif></a> multiple-subscripted arrays <a href="%s9p0"><img src=iicons/bullbib.gif></a> <a href="%s9p0"><img src=iicons/bullbib.gif></a> <a href="%s9p5"><img src=iicons/bullbib.gif></a> N name of an array <a href="%s2p1"><img src=iicons/bullbib.gif></a> named constant <a href="%s4p4"><img src=iicons/bullbib.gif></a> </page> <page> null character '\\0' <a href="%s4p13"><img src=iicons/bullbib.gif></a> O off-by-one errors <a href="^Errors::c:s0p1"><img src=iicons/bullbib.gif></a> P passing arrays to functions <a href="%s5p0"><img src=iicons/bullbib.gif></a> <a href="%s7p2"><img src=iicons/bullbib.gif></a> position number <a href="%s2p0"><img src=iicons/bullbib.gif></a> R row subscript <a href="^Illustration::c:s0p4"><img src=iicons/bullbib.gif></a> S scalable <a href="%s4p4"><img src=iicons/bullbib.gif></a> scalar <a href="%s5p2"><img src=iicons/bullbib.gif></a> search key <a href="%s8p1"><img src=iicons/bullbib.gif></a> <a href="%s8p2"><img src=iicons/bullbib.gif></a> searching arrays <a href="%s8p0"><img src=iicons/bullbib.gif></a> </page> <page> simulated call-by- reference <a href="%s5p6"><img src=iicons/bullbib.gif></a> sinking sort <a href="%s6p1"><img src=iicons/bullbib.gif></a> sorting arrays <a href="%s6p0"><img src=iicons/bullbib.gif></a> string literal <a href="%s4p13"><img src=iicons/bullbib.gif></a> <a href="%s4p17"><img src=iicons/bullbib.gif></a> subscript <a href="%s2p1"><img src=iicons/bullbib.gif></a> T tables of values <a href="%s9p0"><img src=iicons/bullbib.gif></a> tabular format <a href="%s4p0"><img src=iicons/bullbib.gif></a> Z zeroth element <a href="%s2p0"><img src=iicons/bullbib.gif></a> </page> </section> <section type=Popup name=Portable title="Portability"> <page> The (normally serious) effects of referencing elements outside the array bounds are system dependent. </page> </section> <section type=Popup name=Illustration title="Illustrations"> <page> <a href="^Illustration::c:s0p2">Fig. 4.1</a> A 12-element array. <a href="^Illustration::c:s0p3">Fig. 4.2</a> Operator precedence and associativity. <a href="^Code::c:s0p0">Fig. 4.3</a> Initializing the elements of an array to zeros. <a href="^Code::c:s0p1">Fig. 4.4</a> Initializing the elements of an array with a declaration. <a href="^Code::c:s0p2">Fig. 4.5</a> Generating values to be placed into elements of an array. <a href="^Code::c:s0p4">Fig. 4.6</a> Correctly initializing and using a constant variable. <a href="^Code::c:s0p3">Fig. 4.7</a> A const object must be initialized. <a href="^Code::c:s0p5">Fig. 4.8</a> Computing the sum of the elements of an array. <a href="^Code::c:s0p6">Fig. 4.9</a> A student poll analysis program. <a href="^Code::c:s0p7">Fig. 4.10</a> A program that prints histograms. <a href="^Code::c:s0p8">Fig. 4.11</a> Dice-rolling program using arrays instead of switch. <a href="^Code::c:s0p9">Fig. 4.12</a> Treating character arrays as strings. <a href="^Code::c:s0p10">Fig. 4.13</a> Comparing static array initialization and automatic array initialization. <a href="^Code::c:s0p11">Fig. 4.14</a> Passing arrays and individual array elements to functions. <a href="^Code::c:s0p12">Fig. 4.15</a> Demonstrating the const type qualifier. <a href="^Code::c:s0p13">Fig. 4.16</a> Sorting an array with bubble sort. <a href="^Code::c:s0p14">Fig. 4.17</a> Survey data analysis program. <a href="^Code::c:s0p15">Fig. 4.19</a> Linear search of an array. <a href="^Code::c:s0p16">Fig. 4.20</a> Binary search of a sorted array. </page> <page> <a href="^Illustration::c:s0p4">Fig. 4.21</a> A double-subscripted array with three rows and four columns. <a href="^Code::c:s0p17">Fig. 4.22</a> Initializing multidimensional arrays. <a href="^Code::c:s0p18">Fig. 4.23</a> Example of using double-subscripted arrays. <a href="^Illustration::c:s0p5">Fig. 4.24</a> The 36 possible outcomes of rolling two dice. <a href="^Illustration::c:s0p6">Fig. 4.25</a> The eight possible moves of the knight. <a href="^Illustration::c:s0p7">Fig. 4.26</a> The 22 squares eliminated by placing a queen in the upper-left corner. </page> <page> <a href="~audio/Ch04/04fig001.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 4.1 - A 12-element array.<img src="graphics/ch04/fig04001.gif" > </page> <page> <a href="~audio/Ch04/04fig002.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 4.2 - Operator precedence and associativity. <img src="graphics/ch04/fig04002.gif" > </page> <page> Fig<a href="~audio/Ch04/04fig021.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>ure 4.21 - A double-subscripted array with three rows and four columns.<img src="graphics/ch04/fig04021.gif" > </page> <page> Figure 4.24 - The 36 possible outcomes of rolling two dice.<img src="graphics/ch04/fig04024.gif" > </page> <page> Figure 4.25 - The eight possible moves of the knight.<img src="graphics/ch04/fig04025.gif" > </page> <page> Figure 4.26 - The 22 squares eliminated by placing a queen in the upper-left corner. <img src="graphics/ch04/fig04026.gif" > </page> </section> <section type=Popup name=Exercises title="Exercises"> <page pagename="Exercise 4.1"> Exercise 4.1 Answer each of the following: a) Lists and tables of values are stored in ________. b) The elements of an array are related by the fact that they have the same ________ and ________. c) The number used to refer to a particular element of an array is called its ________. d) A ________ should be used to declare the size of an array because it makes the program more scalable. e) The process of placing the elements of an array in order is called ________ the array. <foreign name="answers" url="^Answers::c:s0p0"> </page> <page pagename="Exercise 4.1"> f) The process of determining if an array contains a certain key value is called ________ the array. g) An array that uses two subscripts is referred to as a ________ array. <foreign name="answers" url="^Answers::c:s0p0"> </page> <page pagename="Exercise 4.2"> Exercise 4.2 State whether the following are true or false. If the answer is false, explain why. a) An array can store many different types of values. b) An array subscript should normally be of data type float. c) If there are fewer initializers in an initializer list than the number of elements in the array, the remaining elements are automatically initialized to the last value in the list of initializers. d) It is an error if an initializer list contains more initializers than there are elements in the array. e) An individual array element that is passed to a function and modified in that function will contain the modified value when the called function completes execution. <foreign name="answers" url="^Answers::c:s0p1"> </page> <page pagename="Exercise 4.3"> Exercise 4.3 Answer the following questions regarding an array called fractions. a) Define a constant variable arraySize initialized to 10. b) Declare an array with arraySize elements of type float and initialize the elements to 0. c) Name the fourth element from the beginning of the array. d) Refer to array element 4. e) Assign the value 1.667 to array element 9. f) Assign the value 3.333 to the seventh element of the array. g) Print array elements 6 and 9 with two digits of precision to the right of the decimal point and show the output that is actually displayed on the screen. <foreign name="answers" url="^Answers::c:s0p2"> </page> <page pagename="Exercise 4.3"> h) Print all the elements of the array using a for repetition structure. Define the integer variable x as a control variable for the loop. Show the output. <foreign name="answers" url="^Answers::c:s0p2"> </page> <page pagename="Exercise 4.4"> Exercise 4.4 Answer the following questions regarding an array called table. a) Declare the array to be an integer array and to have 3 rows and 3 columns. Assume the constant variable arraySize has been defined to be 3. b) How many elements does the array contain? c) Use a for repetition structure to initialize each element of the array to the sum of its subscripts. Assume the integer variables x and y are declared as control variables. d) Write a program segment to print the values of each element of array table in tabular format with 3 rows and 3 columns. Assume the array was initialized with the declaration, <foreign name="answers" url="^Answers::c:s0p4"> </page> <page pagename="Exercise 4.4"> <pre> int table[ arraySize ][ arraySize ] = { { 1, 8 }, { 2, 4, 6 }, { 5 } }; </pre> and the integer variables x and y are declared as control variables. Show the output. <foreign name="answers" url="^Answers::c:s0p4"> </page> <page pagename="Exercise 4.5"> Exercise 4.5 Find the error in each of the following program segments and correct the error. <pre> a) #include <iostream.h>; b) arraySize = 10; // arraySize was declared const </pre> c) Assume int b[ 10 ] = { 0 }; <pre> for ( int i = 0; i <= 10; i++ ) b[ i ] = 1; </pre> d) Assume <tt>int a[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; </tt> <pre> a[ 1, 1 ] = 5; </pre> <foreign name="answers" url="^Answers::c:s0p6"> </page> <page pagename="Exercise 4.6"> Exercise 4.6 Fill in the blanks in each of the following: a) C++ stores lists of values in ________. b) The elements of an array are related by the fact that they ________. c) When referring to an array element, the position number contained within parentheses is called a ________. d) The names of the four elements of array p are _____, _____, ________, and ________. e) Naming an array, stating its type, and specifying the number of elements in the array is called ________ the array. f) The process of placing the elements of an array into either ascending or descending order is called ________. </page> <page pagename="Exercise 4.6"> g) In a double-subscripted array, the first subscript (by convention) identifies the ________ of an element, and the second subscript (by convention) identifies the ________ of an element. h) An m-by-n array contains ________ rows, ________ columns, and _______ elements. i) The name of the element in row 3 and column 5 of array d is ________. </page> <page pagename="Exercise 4.7"> Exercise 4.7 State which of the following are true and which are false; for those that are false, explain why they are false. a) To refer to a particular location or element within an array, we specify the name of the array and the value of the particular element. b) An array declaration reserves space for the array. c) To indicate that 100 locations should be reserved for integer array p, the programmer writes the declaration <pre> <spacer width=20 height=1><spacer width=20 height=1>p[ 100 ]; </pre> d) A C++ program that initializes the elements of a 15-element array to zero must contain at least one for statement. </page> <page pagename="Exercise 4.7"> e) A C++ program that totals the elements of a double-subscripted array must contain nested for statements. </page> <page pagename="Exercise 4.8"> Exercise 4.8 Write C++ statements to accomplish each of the following: a) Display the value of the seventh element of character array f. b) Input a value into element 4 of single-subscripted floating-point array b. c) Initialize each of the 5 elements of single-subscripted integer array g to 8. d) Total and print the elements of floating-point array c of 100 elements. e) Copy array a into the first portion of array b. Assume float a[ 11 ], b[ 34 ]; f) Determine and print the smallest and largest values contained in 99-element floating-point array w. </page> <page pagename="Exercise 4.9"> Exercise 4.9 Consider a 2-by-3 integer array t. a) Write a declaration for t. b) How many rows does t have? c) How many columns does t have? d) How many elements does t have? e) Write the names of all the elements in the second row of t. f) Write the names of all the elements in the third column of t. g) Write a single statement that sets the element of t in row 1 and column 2 to zero. h) Write a series of statements that initializes each element of t to zero. Do not use a repetition structure. </page> <page pagename="Exercise 4.9"> i) Write a nested for structure that initializes each element of t to zero. j) Write a statement that inputs the values for the elements of t from the terminal. k) Write a series of statements that determines and prints the smallest value in array t. l) Write a statement that displays the elements of the first row of t. m) Write a statement that totals the elements of the fourth column of t. n) Write a series of statements that prints the array t in neat, tabular format. List the column subscripts as headings across the top and list the row subscripts at the left of each row. </page> <page pagename="Exercise 4.10"> Exercise 4.10 Use a single-subscripted array to solve the following problem. A company pays its salespeople on a commission basis. The salespeople receive $200 per week plus 9 percent of their gross sales for that week. For example, a salesperson who grosses $5000 in sales in a week receives $200 plus 9 percent of $5000, or a total of $650. Write a program (using an array of counters) that determines how many of the salespeople earned salaries in each of the following ranges (assume that each salesperson's salary is truncated to an integer amount): a) $200-$299 b) $300-$399 c) $400-$499 d) $500-$599 <foreign name="answers" url="^Answers::c:s0p8"> </page> <page pagename="Exercise 4.10"> e) $600-$699 f) $700-$799 g) $800-$899 h) $900-$999 i) $1000 and over <foreign name="answers" url="^Answers::c:s0p8"> </page> <page pagename="Exercie 4.11"> Exercie 4.11 The bubble sort presented in <a href="^Code::c:s0p13"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.16 </a>is inefficient for large arrays. Make the following simple modifications to improve the performance of the bubble sort. a) After the first pass, the largest number is guaranteed to be in the highest- numbered element of the array; after the second pass, the two highest numbers are "in place," and so on. Instead of making nine comparisons on every pass, modify the bubble sort to make eight comparisons on the second pass, seven on the third pass, and so on. b) The data in the array may already be in the proper order or near-proper order, so why make nine passes if fewer will suffice? Modify the sort to check at the end of each pass if any swaps have been made. If none has been made, then the </page> <page pagename="Exercie 4.11"> data must already be in the proper order, so the program should terminate. If swaps have been made, then at least one more pass is needed. </page> <page pagename="Exercise 4.12"> Exercise 4.12 Write single statements that perform the following single-subscripted array operations: a) Initialize the 10 elements of integer array counts to zeros. b) Add 1 to each of the 15 elements of integer array bonus. c) Read 12 values for float array monthlyTemperatures from the keyboard. d) Print the 5 values of integer array bestScores in column format. <foreign name="answers" url="^Answers::c:s0p7"> </page> <page pagename="Exercise 4.13"> Exercise 4.13 Find the error(s) in each of the following statements: a) Assume: char str[ 5 ]; <pre> cin >> str; // User types hello </pre> b) Assume: int a[ 3 ]; <pre> cout << a[ 1 ] << " " << a[ 2 ] << " " << a[ 3 ] << endl; float f[ 3 ] = { 1.1, 10.01, 100.001, 1000.0001 }; </pre> d) Assume: double d[ 2 ][ 10 ]; <pre> d[ 1, 9 ] = 2.345; </pre> </page> <page pagename="Exercise 4.14"> Exercise 4.14 Modify the program of <a href="^Code::c:s0p14"> <img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.17</a> so function mode is capable of handling a tie for the mode value. Also modify function median so the two middle elements are averaged in an array with an even number of elements. </page> <page pagename="Exercise 4.15"> Exercise 4.15 Use a single-subscripted array to solve the following problem. Read in 20 numbers, each of which is between 10 and 100, inclusive. As each number is read, print it only if it is not a duplicate of a number already read. Provide for the "worst case" in which all 20 numbers are different. Use the smallest possible array to solve this problem. <foreign name="answers" url="^Answers::c:s0p9"> </page> <page pagename="Exercise 4.16"> Exercise 4.16 Label the elements of 3-by-5 double-subscripted array sales to indicate the order in which they are set to zero by the following program segment: <pre> for ( row = 0; row < 3; row++ ) for ( column = 0; column < 5; column++ ) sales[ row ][ column ] = 0; </pre> </page> <page pagename="Exercise 4.17"> Exercise 4.17 Write a program that simulates the rolling of two dice. The program should use rand to roll the first die, and should use rand again to roll the second die. The sum of the two values should then be calculated. Note: Since each die can show an integer value from 1 to 6, then the sum of the two values will vary from 2 to 12 with 7 being the most frequent sum and 2 and 12 being the least frequent sums. <a href="^Illustration::c:s0p5"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 4.24</a> shows the 36 possible combinations of the two dice. Your program should roll the two dice 36,000 times. Use a single-subscripted array to tally the numbers of times each possible sum appears. Print the results in a tabular format. Also, determine if the totals are reasonable, i.e., there are six ways to roll a 7, so approximately one sixth of all the rolls should be 7. </page> <page pagename="Exercise 4.18"> Exercise 4.18 What does the following program do? <pre> 1 // ex04_18.cpp 2 #include <iostream.h> 3 4 int whatIsThis( int [], int ); 5 6 int main() 7 { 8 const int arraySize = 10; 9 int a[ arraySize ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 10 11 int result = whatIsThis( a, arraySize ); 12 </pre> </page> <page pagename="Exercise 4.18"> <pre> 13 cout << "Result is " << result << endl; </pre> <pre> 14 return 0; 15 } 16 17 int whatIsThis( int b[], int size ) 18 { 19 if ( size == 1 ) 20 return b[ 0 ]; 21 else 22 return b[ size - 1 ] + whatIsThis( b, size - 1 ); 23 } </pre> </page> <page pagename="Exercise 4.19"> Exercise 4.19 Write a program that runs 1000 games of craps and answers the following questions: a) How many games are won on the first roll, second roll, \xc9 , twentieth roll, and after the twentieth roll? b) How many games are lost on the first roll, second roll, \xc9 , twentieth roll, and after the twentieth roll? c) What are the chances of winning at craps? (Note: You should discover that craps is one of the fairest casino games. What do you suppose this means?) d) What is the average length of a game of craps? e) Do the chances of winning improve with the length of the game? </page> <page pagename="Exercise 4.20"> Exercise 4.20 (Airline Reservations System) A small airline has just purchased a computer for its new automated reservations system. You have been asked to program the new system. You are to write a program to assign seats on each flight of the airline's only plane (capacity: 10 seats). <spacer width=20 height=1>Your program should display the following menu of alternatives--Please type 1 for "smoking" and Please type 2 for "nonsmoking". If the person types 1, your program should assign a seat in the smoking section (seats 1-5). If the person types 2, your program should assign a seat in the nonsmoking section (seats 6-10). Your program should print a boarding pass indicating the person's seat number and whether it is in the smoking or nonsmoking section of the plane. <foreign name="answers" url="^Answers::c:s0p10"> </page> <page pagename="Exercise 4.20"> <spacer width=20 height=1>Use a single-subscripted array to represent the seating chart of the plane. Initialize all the elements of the array to 0 to indicate that all seats are empty. As each seat is assigned, set the corresponding elements of the array to 1 to indicate that the seat is no longer available. <spacer width=20 height=1>Your program should, of course, never assign a seat that has already been assigned. When the smoking section is full, your program should ask the person if it is acceptable to be placed in the nonsmoking section (and vice versa). If yes, then make the appropriate seat assignment. If no, then print the message "Next flight leaves in 3 hours." <foreign name="answers" url="^Answers::c:s0p10"> </page> <page pagename="Exercise 4.21"> Exercise 4.21 What does the following program do? <pre> 1 // ex04_21.cpp 2 #include <iostream.h> 3 4 void someFunction( int [], int ); 5 6 int main() 7 { 8 const int arraySize = 10; 9 int a[ arraySize ] = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 }; 10 11 cout << "The values in the array are:" << endl; </pre> </page> <page pagename="Exercise 4.21"> <pre> 12 someFunction( a, arraySize ); </pre> <pre> 13 cout << endl; 14 return 0; 15 } 16 17 void someFunction( int b[], int size ) 18 { 19 if ( size > 0 ) { 20 someFunction( &b[ 1 ], size - 1 ); 21 cout << b[ 0 ] << " "; 22 } 23 } </pre> </page> <page pagename="Exercise 4.22"> Exercise 4.22 Use a double-subscripted array to solve the following problem. A company has four salespeople (1 to 4) who sell five different products (1 to 5). Once a day, each salesperson passes in a slip for each different type of product sold. Each slip contains: a) The salesperson number b) The product number c) The total dollar value of that product sold that day Thus, each salesperson passes in between 0 and 5 sales slips per day. Assume that the information from all of the slips for last month is available. Write a program that will read all this information for last month's sales, and summarize the total sales by salesperson by product. All totals should be stored in the </page> <page pagename="Exercise 4.22"> double-subscripted array sales. After processing all the information for last month, print the results in tabular format with each of the columns representing a particular salesperson and each of the rows representing a particular product. Cross total each row to get the total sales of each product for last month; cross total each column to get the total sales by salesperson for last month. Your tabular printout should include these cross totals to the right of the totaled rows and to the bottom of the totaled columns. </page> <page pagename="Exercise 4.23"> Exercise 4.23 (Turtle Graphics) The Logo language, which is particularly popular among personal computer users, made the concept of turtle graphics famous. Imagine a mechanical turtle that walks around the room under the control of a C++ program. The turtle holds a pen in one of two positions, up or down. While the pen is down, the turtle traces out shapes as it moves; while the pen is up, the turtle moves about freely without writing anything. In this problem you will simulate the operation of the turtle and create a computerized sketchpad as well. <spacer width=20 height=1>Use a 20-by-20 array floor which is initialized to zeros. Read commands from an array that contains them. Keep track of the current position of the turtle at all times and whether the pen is currently up or down. Assume that the turtle always <foreign name="answers" url="^Answers::c:s0p11"> </page> <page pagename="Exercise 4.23"> starts at position 0,0 of the floor with its pen up. The set of turtle commands your program must process are as follows: <img src="graphics/ch04/ex04023.gif" > <foreign name="answers" url="^Answers::c:s0p11"> </page> <page pagename="Exercise 4.23"> Suppose that the turtle is somewhere near the center of the floor. The following "program" would draw and print a 12-by 12-square leaving the pen in the up position: <foreign name="answers" url="^Answers::c:s0p11"> </page> <page pagename="Exercise 4.23"> 6 9 As the turtle moves with the pen down, set the appropriate elements of array floor to 1s. When the 6 command (print) is given, wherever there is a 1 in the array, display an asterisk, or some other character you choose. Wherever there is a zero display a blank. Write a program to implement the turtle graphics capabilities discussed here. Write several turtle graphics programs to draw interesting shapes. Add other commands to increase the power of your turtle graphics language. <foreign name="answers" url="^Answers::c:s0p11"> </page> <page pagename="Exercise 4.24"> Exercise 4.24 (Knight's Tour) One of the more interesting puzzlers for chess buffs is the Knight's Tour problem, originally proposed by the mathematician Euler. The question is this: Can the chess piece called the knight move around an empty chessboard and touch each of the 64 squares once and only once? We study this intriguing problem in depth here. <spacer width=20 height=1>The knight makes L-shaped moves (over two in one direction and then over one in a perpendicular direction). Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered 0 through 7) as shown in <a href="^Illustration::c:s0p6"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 4.25</a>. a) Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight's Tour by hand. Put a 1 in the first square you move to, a 2 in the second square, a 3 in </page> <page pagename="Exercise 4.24"> the third, etc. Before starting the tour, estimate how far you think you will get, remembering that a full tour consists of 64 moves. How far did you get? Was this close to your estimate? b) Now let us develop a program that will move the knight around a chessboard. The board is represented by an 8-by-8 double-subscripted array board. Each of the squares is initialized to zero. We describe each of the eight possible moves in terms of both their horizontal and vertical components. For example, a move of type 0 as shown in <a href="^Illustration::c:s0p6"> <img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 4.25</a> consists of moving two squares horizontally to the right and one square vertically upward. Move 2 consists of moving one square horizontally to the left and two squares vertically upward. Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The </page> <page pagename="Exercise 4.24"> eight moves may be described by two single-subscripted arrays, horizontal and vertical, as follows: <pre> horizontal[ 0 ] = 2 horizontal[ 1 ] = 1 horizontal[ 2 ] = -1 horizontal[ 3 ] = -2 horizontal[ 4 ] = -2 horizontal[ 5 ] = -1 horizontal[ 6 ] = 1 horizontal[ 7 ] = 2 vertical[ 0 ] = -1 vertical[ 1 ] = -2 vertical[ 2 ] = -2 vertical[ 3 ] = -1 vertical[ 4 ] = 1 </pre> </page> <page pagename="Exercise 4.24"> <pre> vertical[ 5 ] = 2 vertical[ 6 ] = 2 vertical[ 7 ] = 1 </pre> Let the variables currentRow and currentColumn indicate the row and column of the knight's current position. To make a move of type moveNumber, where moveNumber is between 0 and 7, your program uses the statements <pre> currentRow += vertical[ moveNumber ]; currentColumn += horizontal[ moveNumber ]; </pre> Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Remember to test each potential move to see if the knight has already visited that square. And, of course, test every potential move to make sure that the knight does not land off the chessboard. Now write a program </page> <page pagename="Exercise 4.24"> to move the knight around the chessboard. Run the program. How many moves did the knight make? c) After attempting to write and run a Knight's Tour program, you have probably developed some valuable insights. We will use these to develop a heuristic (or strategy) for moving the knight. Heuristics do not guarantee success, but a carefully developed heuristic greatly improves the chance of success. You may have observed that the outer squares are more troublesome than the squares nearer the center of the board. In fact, the most troublesome, or inaccessible, squares are the four corners. Intuition may suggest that you should attempt to move the knight to the most troublesome squares first and leave open those that are easiest to get to so when </page> <page pagename="Exercise 4.24"> the board gets congested near the end of the tour there will be a greater chance of success. We may develop an "accessibility heuristic" by classifying each of the squares according to how accessible they are, and then always moving the knight to the square (within the knight's L-shaped moves, of course) that is most inaccessible. We label a double-subscripted array accessibility with numbers indicating from how many squares each particular square is accessible. On a blank chessboard, each center square is rated as 8, each corner square is rated as 2, and the other squares have accessibility numbers of 3, 4, or 6 as follows: </page> <page pagename="Exercise 4.24"> <pre> 2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2 </pre> Now write a version of the Knight's Tour program using the accessibility heuristic. At any time, the knight should move to the square with the lowest accessibility number. In case of a tie, the knight may move to any of the tied squares. Therefore, the tour may begin in any of the four corners. (Note: As the knight moves around the chessboard, your program should reduce the </page> <page pagename="Exercise 4.24"> accessibility numbers as more and more squares become occupied. In this way, at any given time during the tour, each available square's accessibility number will remain equal to precisely the number of squares from which that square may be reached.) Run this version of your program. Did you get a full tour? Now modify the program to run 64 tours, one starting from each square of the chessboard. How many full tours did you get? d) Write a version of the Knight's Tour program which, when encountering a tie between two or more squares, decides what square to choose by looking ahead to those squares reachable from the "tied" squares. Your program should move to the square for which the next move would arrive at a square with the lowest accessibility number. </page> <page pagename="Exercise 4.25"> Exercise 4.25 (Knight's Tour: Brute Force Approaches) In <a href="^Exercises::c:s0p38"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 4.24</a> we developed a solution to the Knight's Tour problem. The approach used, called the "accessibility heuristic," generates many solutions and executes efficiently. <spacer width=20 height=1>As computers continue increasing in power, we will be able to solve more problems with sheer computer power and relatively unsophisticated algorithms. Let us call this approach "brute force" problem solving. a) Use random number generation to enable the knight to walk around the chess board (in its legitimate L-shaped moves, of course) at random. Your program should run one tour and print the final chessboard. How far did the knight get? b) Most likely, the preceding program produced a relatively short tour. Now modify your program to attempt 1000 tours. Use a single-subscripted array to </page> <page pagename="Exercise 4.25"> keep track of the number of tours of each length. When your program finishes attempting the 1000 tours, it should print this information in neat tabular format. What was the best result? c) Most likely, the preceding program gave you some "respectable" tours but no full tours. Now "pull all the stops out" and simply let your program run until it produces a full tour. (Caution: This version of the program could run for hours on a powerful computer.) Once again, keep a table of the number of tours of each length, and print this table when the first full tour is found. How many tours did your program attempt before producing a full tour? How much time did it take? d) Compare the brute force version of the Knight's Tour with the accessibility heuristic version. Which required a more careful study of the problem? Which </page> <page pagename="Exercise 4.25"> algorithm was more difficult to develop? Which required more computer power? Could we be certain (in advance) of obtaining a full tour with the accessibility heuristic approach? Could we be certain (in advance) of obtaining a full tour with the brute force approach? Argue the pros and cons of brute force problem solving in general. </page> <page pagename="Exercise 4.26"> Exercise 4.26 (Eight Queens) Another puzzler for chess buffs is the Eight Queens problem. Simply stated: Is it possible to place eight queens on an empty chessboard so that no queen is "attacking" any other, i.e., no two queens are in the same row, the same column, or along the same diagonal? Use the thinking developed in <a href="^Exercises::c:s0p38"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 4.24</a> to formulate a heuristic for solving the Eight Queens problem. Run your program. (Hint: It is possible to assign a value to each square of the chessboard indicating how many squares of an empty chessboard are "eliminated" if a queen is placed in that square. Each of the corners would be assigned the value 22, as in <a href="^Illustration::c:s0p7"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 4.26</a>.) Once these "elimination numbers" are placed in all 64 squares, an appropriate heuristic might be: Place the next queen </page> <page pagename="Exercise 4.26"> in the square with the smallest elimination number. Why is this strategy intuitively appealing? </page> <page pagename="Exercise 4.27"> Exercise 4.27 (Eight Queens: Brute Force Approaches) In this exercise you will develop several brute force approaches to solving the Eight Queens problem introduced in <a href="^Exercises::c:s0p49"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 4.26</a>. a) Solve the Eight Queens exercise, using the random brute force technique developed in <a href="^Exercises::c:s0p46"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 4.25</a>. b) Use an exhaustive technique, i.e., try all possible combinations of eight queens on the chessboard. c) Why do you suppose the exhaustive brute force approach may not be appropriate for solving the Knight's Tour problem? d) Compare and contrast the random brute force and exhaustive brute force approaches in general. </page> <page pagename="Exercise 4.28"> Exercise 4.28 (Knight's Tour: Closed Tour Test) In the Knight's Tour, a full tour occurs when the knight makes 64 moves touching each square of the chess board once and only once. A closed tour occurs when the 64th move is one move away from the location in which the knight started the tour. Modify the Knight's Tour program you wrote in <a href="^Exercises::c:s0p38"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 4.24</a> to test for a closed tour if a full tour has occurred. </page> <page pagename="Exercise 4.29"> Exercise 4.29 (The Sieve of Eratosthenes) A prime integer is any integer that is evenly divisible only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It operates as follows: a) Create an array with all elements initialized to 1 (true). Array elements with prime subscripts will remain 1. All other array elements will eventually be set to zero. b) Starting with array subscript 2 (subscript 1 must be prime), every time an array element is found whose value is 1, loop through the remainder of the array and set to zero every element whose subscript is a multiple of the subscript for the element with value 1. For array subscript 2, all elements beyond 2 in the array that are multiples of 2 will be set to zero (subscripts 4, 6, 8, 10, etc.); for <foreign name="answers" url="^Answers::c:s0p12"> </page> <page pagename="Exercise 4.29"> array subscript 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (subscripts 6, 9, 12, 15, etc.); and so on. When this process is complete, the array elements that are still set to one indicate that the subscript is a prime number. These subscripts can then be printed. Write a program that uses an array of 1000 elements to determine and print the prime numbers between 1 and 999. Ignore element 0 of the array. <foreign name="answers" url="^Answers::c:s0p12"> </page> <page pagename="Exercise 4.30"> Exercise 4.30 (Bucket Sort) A bucket sort begins with a single-subscripted array of positive integers to be sorted, and a double-subscripted array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n - 1 where n is the number of values in the array to be sorted. Each row of the double-subscripted array is referred to as a bucket. Write a function bucketSort that takes an integer array and the array size as arguments and performs as follows: a) Place each value of the single-subscripted array into a row of the bucket array based on the value's ones digit. For example, 97 is placed in row 7, 3 is placed in row 3, and 100 is placed in row 0. This is called a "distribution pass." <foreign name="answers" url="^Answers::c:s0p13"> </page> <page pagename="Exercise 4.30"> b) Loop through the bucket array row-by-row and copy the values back to the original array. This is called a "gathering pass." The new order of the preceding values in the single-subscripted array is 100, 3, and 97. c) Repeat this process for each subsequent digit position (tens, hundreds, thousands, etc.). On the second pass, 100 is placed in row 0, 3 is placed in row 0 (because 3 has no tens digit), and 97 is placed in row 9. After the gathering pass, the order of the values in the single-subscripted array is 100, 3, and 97. On the third pass, 100 is placed in row 1, 3 is placed in row zero and 97 is placed in row zero (after the 3). After the last gathering pass, the original array is now in sorted order. <spacer width=20 height=1>Note that the double-subscripted array of buckets is ten times the size of the integer array being sorted. This sorting technique provides better performance <foreign name="answers" url="^Answers::c:s0p13"> </page> <page pagename="Exercise 4.30"> than a bubble sort, but requires much more memory. The bubble sort requires space for only one additional element of data. This is an example of the space- time tradeoff: The bucket sort uses more memory than the bubble sort, but performs better. This version of the bucket sort requires copying all the data back to the original array on each pass. Another possibility is to create a second double-subscripted bucket array and repeatedly swap the data between the two bucket arrays. <foreign name="answers" url="^Answers::c:s0p13"> </page> <page pagename="Recursion Exercises"> Recursion Exercises </page> <page pagename="Exercise 4.31"> Exercise 4.31 (Selection Sort) A selection sort searches an array looking for the smallest element in the array. Then, the smallest element is swapped with the first element of the array. The process is repeated for the subarray beginning with the second element of the array. Each pass of the array results in one element being placed in its proper location. This sort performs comparably to the bubble sort-- for an array of n elements, n - 1 passes must be made, and for each subarray, n - 1 comparisons must be made to find the smallest value. When the subarray being processed contains one element, the array is sorted. Write recursive function selectionSort to perform this algorithm. </page> <page pagename="Exercise 4.32"> Exercise 4.32 (Palindromes) A palindrome is a string that is spelled the same way forwards and backwards. Some examples of palindromes are: "radar," "able was i ere i saw elba," and (if blanks are ignored) "a man a plan a canal panama." Write a recursive function testPalindrome that returns true if the string stored in the array is a palindrome, and false otherwise. The function should ignore spaces and punctuation in the string. </page> <page pagename="Exercise 4.33"> Exercise 4.33 (Linear Search) Modify <a href="^Code::c:s0p15"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.19</a> to use recursive function linearSearch to perform a linear search of the array. The function should receive an integer array and the size of the array as arguments. If the search key is found, return the array subscript; otherwise, return 1. <foreign name="answers" url="^Answers::c:s0p14"> </page> <page pagename="Exercise 4.34"> Exercise 4.34 (Binary Search) Modify the program of <a href="^Code::c:s0p16"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 4.20</a> to use a recursive function binarySearch to perform the binary search of the array. The function should receive an integer array and the starting subscript and ending subscript as arguments. If the search key is found, return the array subscript; otherwise, return 1. </page> <page pagename="Exercise 4.35"> Exercise 4.35 (Eight Queens) Modify the Eight Queens program you created in <a href="^Exercises::c:s0p49"> <img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 4.26</a> to solve the problem recursively. </page> <page pagename="Exercise 4.36"> Exercise 4.36 (Print an array) Write a recursive function printArray that takes an array and the size of the array as arguments and returns nothing. The function should stop processing and return when it receives an array of size zero. <foreign name="answers" url="^Answers::c:s0p15"> </page> <page pagename="Exercise 4.37"> Exercise 4.37 (Print a string backwards) Write a recursive function stringReverse that takes a character array containing a string as an argument, prints the string backwards, and returns nothing. The function should stop processing and return when the terminating null character is encountered. </page> <page pagename="Exercise 4.38"> Exercise 4.38 (Find the minimum value in an array) Write a recursive function recursiveMinimum that takes an integer array and the array size as arguments and returns the smallest element of the array. The function should stop processing and return when it receives an array of 1 element. <foreign name="answers" url="^Answers::c:s0p16"> </page> </section> <section type=Popup name=Objective title="Objectives"> <page> <indent width=8 delay>* To introduce the array data structure.</indent> <indent width=8 delay>* To understand the use of arrays to store, sort, and search lists and tables of values. </indent> <indent width=8 delay>* To understand how to declare an array, initialize an array, and refer to individual elements of an array.</indent> <foreign name="audio" url="~audio/Ch04/04obj.au"> </page> <page> <indent width=8 delay>* To be able to pass arrays to functions.</indent> <indent width=8 delay>* To understand basic sorting techniques.</indent> <indent width=8 delay>* To be able to declare and manipulate multiple-subscript arrays.</indent> </page> </section> <section type=Popup name=Code title="Code Examples"> <page> Figure 4.3 Initializing the elements of an array to zeros. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_03.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_03.jar"> <foreign name="audio" url="~audio/Ch04/04fig003.au"> <foreign name="execute" url="!jarexe Run/fig04_03.jar"> </page> <page> Figure 4.4 Initializing the elements of an array with a declaration. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_04.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_04.jar"> <foreign name="audio" url="~audio/Ch04/04fig004.au"> <foreign name="execute" url="!jarexe Run/fig04_04.jar"> </page> <page> Figure 4.5 Generating values to be placed into elements of an array. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_05.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_05.jar"> <foreign name="audio" url="~audio/Ch04/04fig005.au"> <foreign name="execute" url="!jarexe Run/fig04_05.jar"> </page> <page> Figure 4.7 A const object must be initialized. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_07.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_07.jar"> <foreign name="audio" url="~audio/Ch04/04fig007.au"> </page> <page> Figure 4.6 Correctly initializing and using a constant variable. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_06.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_06.jar"> <foreign name="audio" url="~audio/Ch04/04fig006.au"> <foreign name="execute" url="!jarexe Run/fig04_06.jar"> </page> <page> Figure 4.8 Computing the sum of the elements of an array. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_08.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_08.jar"> <foreign name="audio" url="~audio/Ch04/04fig008.au"> <foreign name="execute" url="!jarexe Run/fig04_08.jar"> </page> <page> Figure 4.9 A student poll analysis program. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_09.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_09.jar"> <foreign name="audio" url="~audio/Ch04/04fig009.au"> <foreign name="execute" url="!jarexe Run/fig04_09.jar"> </page> <page> Figure 4.10 A program that prints histograms. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_10.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_10.jar"> <foreign name="audio" url="~audio/Ch04/04fig010.au"> <foreign name="execute" url="!jarexe Run/fig04_10.jar"> </page> <page> Figure 4.11 Dice-rolling program using arrays instead of switch. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_11.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_11.jar"> <foreign name="audio" url="~audio/Ch04/04fig011.au"> <foreign name="execute" url="!jarexe Run/fig04_11.jar"> </page> <page> Figure 4.12 Treating character arrays as strings. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_12.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_12.jar"> <foreign name="audio" url="~audio/Ch04/04fig012.au"> <foreign name="execute" url="!jarexe Run/fig04_12.jar"> </page> <page> Figure 4.13 Comparing static array initialization and automatic array initialization. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_13.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_13.jar"> <foreign name="audio" url="~audio/Ch04/04fig013.au"> <foreign name="execute" url="!jarexe Run/fig04_13.jar"> </page> <page> Figure 4.14 Passing arrays and individual array elements to functions. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_14.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_14.jar"> <foreign name="audio" url="~audio/Ch04/04fig014.au"> <foreign name="execute" url="!jarexe Run/fig04_14.jar"> </page> <page> Figure 4.15 Demonstrating the const type qualifier. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_15.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_15.jar"> <foreign name="audio" url="~audio/Ch04/04fig015.au"> </page> <page> Figure 4.16 Sorting an array with bubble sort. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_16.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_16.jar"> <foreign name="audio" url="~audio/Ch04/04fig016.au"> <foreign name="execute" url="!jarexe Run/fig04_16.jar"> </page> <page> Figure 4.17 Survey data analysis program. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_17.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_17.jar"> <foreign name="audio" url="~audio/Ch04/04fig017.au"> <foreign name="execute" url="!jarexe Run/fig04_17.jar"> </page> <page> Figure 4.19 Linear search of an array. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_19.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_19.jar"> <foreign name="audio" url="~audio/Ch04/04fig019.au"> <foreign name="execute" url="!jarexe Run/fig04_19.jar"> </page> <page> Figure 4.20 Binary search of a sorted array. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_20.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_20.jar"> <foreign name="audio" url="~audio/Ch04/04fig020.au"> <foreign name="execute" url="!jarexe Run/fig04_20.jar"> </page> <page> Figure 4.22 Initializing multidimensional arrays. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_22.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_22.jar"> <foreign name="audio" url="~audio/Ch04/04fig022.au"> <foreign name="execute" url="!jarexe Run/fig04_22.jar"> </page> <page> Figure 4.23 Example of using double-subscripted arrays. <applet code=gsl.win.helper.TextBox width=580 height=300> <param name="file" value="code/ch04/fig04_23.txt"> </applet> <foreign name="copy2disk" url="!jcpy Source/fig04_23.jar"> <foreign name="audio" url="~audio/Ch04/04fig023.au"> <foreign name="execute" url="!jarexe Run/fig04_23.jar"> </page> </section> <section type=Popup name=Perform title="Performance"> <page> If, instead of initializing an array with execution time assignment statements, you initialize the array at compile time with an array initializer list, your program will execute faster. </page> <page> Sometimes performance considerations far outweigh clarity considerations. </page> <page> We can apply static to a local array declaration so the array is not created and initialized each time the function is called, and the array is not destroyed each time the function is exited in the program. </page> <page> This improves performance. </page> <page> Passing arrays simulated call-by- reference makes sense for performance reasons. If arrays were passed call-by-value, a copy of each element would be passed. For large, frequently passed arrays, this would be </page> <page> time consuming and would consume considerable storage for the copies of the arrays. </page> <page> Sometimes, the simplest algorithms perform poorly. Their virtue is that they are easy to write, test and debug. More complex algorithms are sometimes needed to realize maximum performance. </page> <page> The tremendous performance gains of the binary search over the linear search do not come without a price. Sorting an array is an expensive operation compared to searching an entire array once for one item. The overhead </page> <page> of sorting an array becomes worthwhile when the array will need to be searched many times at high speed. </page> </section> <section type=Popup name=Practice title="Good Practices"> <page> Defining the size of an array as a constant variable instead of a constant makes programs clearer. This technique is used to get rid of so-called magic numbers; i.e., repeatedly mentioning the size 10, for </page> <page> example, in array processing code for a 10-element array gives the number 10 an artificial significance and may unfortunately confuse the reader when the program includes other 10s that </page> <page> have nothing to do with the array size. </page> <page> Strive for program clarity. It is sometimes worthwhile to trade off the most efficient use of memory or processor time in favor of writing clearer programs. </page> <page> Some programmers include variable names in function prototypes to make programs clearer. The compiler ignores these names. </page> </section> <section type=Popup name=Errors title="Common Errors"> <page> It is important to note the difference between the "seventh element of the array" and "array element seven." Because array subscripts begin at 0, the "seventh element of the array" has a subscript of 6, while </page> <page> "array element seven" has a subscript of 7 and is actually the eighth element of the array. Unfortunately, this is a source of "off-by-one" errors. </page> <page> Providing more initializers in an array initializer list than there are elements in the array is a syntax error. </page> <page> Forgetting to initialize the elements of an array whose elements should be initialized is a logic error. </page> <page> Assigning a value to a constant variable in an executable statement is a syntax error. </page> <page> Only constants can be used to declare automatic and static arrays. Not using a constant for this purpose is a syntax error. </page> <page> Referring to an element outside the array bounds is an execution- time logic error. It is not a syntax error. </page> <page> Although it is possible to use the same counter variable in a for loop and a second for loop nested inside, this is normally a logic error. </page> <page> Not providing cin >> with a character array large enough to store a string typed at the keyboard can result in loss of data in a program and other serious run-time errors. </page> <page> Assuming that elements of a function's local static array are initialized to zero every time the function is called can lead to logic errors in a program. </page> <page> Forgetting that arrays are passed by reference and hence can be modified may result in a logic error. </page> <page> Referencing a double- subscripted array element a[ x ][ y ] incorrectly as a[ x, y ]. Actually, a[ x, y ] is treated as a[ y ] because C++ evaluates the expression (containing a comma operator) x, y simply as y (the last of </page> <page> the comma-separated expressions). </page> </section> <section type=Popup name=Engineer title="Engineering"> <page> Defining the size of each array as a constant variable instead of a constant makes programs more scalable. </page> <page> It is possible to pass an array by value (by using a simple trick we explain in Chapter 6)-- this is rarely done. </page> <page> The const type qualifier can be applied to an array parameter in a function definition to prevent the original array from being modified in the function body. This is another example of the principle of least </page> <page> privilege. Functions should not be given the capability to modify an array unless it is absolutely necessary. </page> </section> <section type=Popup name=AppletPopup title="Applet Examples"> <page> This chapter does not contain any Applet Examples. </page> </section> </chapter> </html> </html>